IMO 2011 en Amsterdam – Problema nº 5

Hoy lunes os propongo el quinto problema de la IMO 2011 celebrada en Amsterdam durante el mes de julio:

Sea f una función del conjunto de los enteros al conjunto de los enteros positivos. Se supone que para cualesquiera dos enteros m y n, la diferencia f(m)-f(n) es divisible por f(m-n). Demostrar que para todos los enteros m y n con f(m) \le f(n), el número f(n) es divisible por f(m).

Que se os dé bien.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

17 Comentarios

  1. Bien, he dado con una solución que, aunque no termina de convencerme, la pongo (y de paso a ver si alguien más se anima).

    Si f(m)|f(n) >> f(n)-f(m)= ax, con a,x€Z*
    Si f(m-n)|f(m)-f(n) >> f(m)-f(n)-f(m-n)= by, con b,y€Z*

    Planteamos las dos ecuaciones como un sistema, de lo que queda:

    -f(m-n)= ax+by

    Por el algoritmo de la división de Euclides sabemos que:

    (x,y)= ax+by, para algún par a,b€Z

    Y por el Teorema de Bézout sabemos que:

    -f(m-n)= (x,y)= ax+by, para algún par a,b€Z

    Luego, cualquier cuaternión (a,b,x,y) que cumpla la propiedad, demuestra el enunciado.

    Correcciones y comentarios serán agradecidos.

    ¡Saludos! Y a disfrutar lo poco que queda de agosto 😉

    Publica una respuesta
  2. Hola Sebastian!

    Tengo una pregunta, demostraste que la función de la cual se habla tiene la forma ax+by. No entendí muy bien lo que demostraste.

    Cordial saludo y sí, a disfrutar lo que queda de Agosto 😀

    Publica una respuesta
  3. Buenas noches Zeta;

    Lo que yo deduzco de mi demostración (que, como dije, no me convence ni a mí, jejeje) es que si f(m)|f(n), existen cuatro enteros {a,b,x,y} que aseguran la divisibilidad de f(m)-f(n)|f(m-n).

    Cualquier corrección es bienvenida, compañero. La ‘cosa’ es que la mayoría de las veces resuelvo los problemas de forma mental; pienso que aquí hubiese sido efectivo las congruencias en módulo cero o la reducción al absurdo, pero el calor veraniego y la mala costumbre de no coger papel y bolígrafo me la pueden haber jugado.

    Pero me alegro que la respuesta despierte tu interés. Vi el post muy ‘muerto’, sin respuestas; quizá tú des con algo mejor.

    Muchos saludos 😉

    Publica una respuesta
  4. Hola de nuevo Sebastian!

    Mmm… veo un problema. Sea P el siguiente hecho:
    P:=”Si para m\leq n, tenemos que f(m)|f(n) , entonces f(m)-f(n)|f(m-n)“.

    P es lo que tu demostraste.

    Si P es cierto podríamos demostrar que la única función que lo cumple es la función cero:

    Por hipótesis del enunciado, f(m-n)|f(m)-f(n), entonces por P, tendríamos que f(m)-f(n)=f(m-n). De este modo, tomando m=n tenemos f(m)-f(m)=f(m-m). Entonces f(0)=0. Por otro lado, como f(m-n)|f(m)-f(n), entonces, tomando n=0, tenemos f(m)|f(m)-f(0). Como f(m)|f(m), necesariamente f(m)|f(0) para todo m. De lo cual podemos deducir que f(m)\leq f(0) para todo m. En conclusión f(m)\leq 0 para todo m. Como la función va de los enteros a los enteros positivos, entonces f(m)=0 para todo m.

    Hemos demostrado que P implica que f es la función cero. Pero ahora vemos que la función f(x)=c donde c es cualquier constante, también cumple las condiciones del enunciado. Contradicción.

    Entonces, no puede pasar P.

    De pasó di una ayuda. f(m)|f(0) para todo m.

    Y sí, es extraño que este post en particular haya quedado muerto, en mi blog pasó lo mismo… más extraño es que, entre los problemas que más solucionaron los participantes correctamente, este ocupó el tercer lugar. El sexto problema… sólo lo solucionaron seis personas de manera correcta.

    Salu2 a to2.

    Publica una respuesta
  5. Yo lo intenté durante algunas horas y no lo conseguí.

    Recuerdo haber demostrado resultados como que, para todo m se cumple que:

    La ya comentada f(m)|f(0)

    f(1)|f(m)

    f(m) = f(-m)

    Pero ahí me quedé.

    Publica una respuesta
  6. Otro resultado que quizás ayude.

    Para todo m entero y k entero positivo, f(m)|f(km).

    La prueba es por inducción.

    Esto junto con el hecho de que la función es par (el tercer resultado de Sive) generaliza a

    Para todo m,k enteros, f(m)|f(km).

    😀 Un saludo.

    Publica una respuesta
  7. Sí también vi eso ZetaSelberg, es una generalización del segundo resultado que puse.

    También demostré que, salvo en f(0), donde hay una especie de singularidad, la función tiene que ser periódica.

    Publica una respuesta
  8. La demostración de que la función es “casi periódica” es curiosa, y mi intuición me dice que se puede sacar petróleo de ella.

    La idea es que, puesto que sabemos que la función tiene un máximo en f(0), eso nos garantiza que existirá también un máximo si nos fijamos únicamente en el dominio de los enteros positivos (en principio este máximo no necesariamente coincidirá con f(0)).

    Supongamos que conocemos el valor mínimo de a, tal que f(a) es este máximo.

    En este caso, dado un b positivo arbitrario, y según enunciado:

    f(a+b-b) | f(a+b) - f(b)

    f(a) | f(a+b) - f(b)

    Pero puesto que f(a) es necesariamente mayor que f(a+b) - f(b), eso nos deja que f(a+b) = f(b)

    Como la función es par, la periodicidad se extiende al dominio negativo.

    En f(0), lo único garantizado es lo que ya sabíamos, que será un múltiplo de f(a).

    Publica una respuesta
  9. Por reducción al absurdo.

    – Hipótesis: f(m-n) no divide a f(m)-f(n)

    Entonces, f(m)-f(n)= cf(m-n)+r, con r≠0

    Por otro lado, f(m)|f(n) para todo f(m)≤f(n), luego

    f(n)= c’f(m)

    Entonces,

    f(m)-f(n)= f(m)-c’f(m)= f(m)[1-c’]= cf(m-n)+r

    De ahí,

    f(m)= cf(m)-cf(n)+r+f(n)

    f(m)= cf(m)+f(n)[1-c]+r

    f(m)[1-c]= f(n)[1-c]+r

    f(m)= f(n)+r/(1-c)

    Dije antes que r≠0, y el único c que anularía el denominador es c= 1.

    Luego no se cumple que todo f(m)|f(n) para f(m)≤f(n).

    Me parece haber llegado a la contradicción que esperaba.

    De nuevo, correcciones y aportaciones son bienvenidas.

    Saludos y buen domingo 😉

    *revisándolo… ¡qué cacao!

    Publica una respuesta
  10. Mmmm, hay algo que no entiendo en tu demostración Sive.

    “Pero puesto que f(a) es necesariamente mayor que f(a+b)-f(b), eso nos deja que f(a)=f(a+b)

    La función f(x)=2 si x par y f(x)=1 si x impar, cumple las condiciones. Tiene máximos en todos los pares, en particular en 2. Si tomamos b=1, entonces, f(3)=1 pero f(2)=2.

    Si bien es cierto que f(a) es mayor a f(a+b)-f(b), no sé como dedujo la igualdad.

    Cordial saludo a todos. 🙂

    Publica una respuesta
  11. ZetaSelberg bueno, ahí hay dos pequeñas errata, una míay otra tuya. La mía la vi después, pero no lo maticé porque pensé que se entendería. Debí poner (en negrita lo que faltaba):

    Pero puesto que f(a) es necesariamente mayor que el valor absoluto de f(a+b)-f(b), eso nos deja que f(b)=f(a+b)

    Y la tuya es que crees que la igualdad es f(a)=f(a+b), cuando no es eso lo que puse.

    La igualdad sale de que el único múltiplo no negativo de x, que es menor que x, es cero. Es decir:

    f(a+b)-f(b) = 0

    f(a+b)=f(b)

    Tu contraejemplo no es tal porque a=2 y b=1, y f(3)=f(1)

    Publica una respuesta
  12. Demostré este problema poco después de mi último comentario. No creo que sea la demostración más breve posible, pero tiene la ventaja de definir exactamente como deben ser las funciones que cumplen el enunciado.

    Este fin de semana, con más tiempo, lo expondré.

    Publica una respuesta
  13. Voy a demostrar unos resultados parciales que ya hemos comentado pero no demostrado. Ya en el siguiente post abordo el problema.

    1) f(a) | f(0) Esto se demuestra aplicando la definición de la función para m=a y n=0

    f(a) - f(0) = k f(a-0)
    f(0) = f(a) - k f(a)

    Dado que los dos sumandos del segundo término son múltiplos de f(a), f(0) también.

    2) f(a) | f(ba) Con b no negativo. Se demuestra fácilmente por inducción. Más adelante, cuando demuestre que la función es par, quedará demostrado también para b negativo.

    Claramente se cumple para b=0 y b=1, así que directamente veo que pasa con b+1, suponiendo que se cumple para b:

    f((b+1)a) - f(a) = k f(ba)
    f((b+1)a) = k f(ba) + f(a)

    Igual que antes, dado que ambos sumandos del segundo término son múltiplos de f(a), también f((b+1)a) lo es.

    3) f(a) = f(-a)

    f(a) - f(-a) = k f(0)

    Pero por 1), sabemos que f(0) es mayor o igual que f(a) y f(-a), por tanto es mayor que el valor absoluto de la diferencia. Por tanto la única posibilidad es que k=0:

    f(a) - f(-a) = 0
    f(a) = f(-a)

    Publica una respuesta
  14. Buff, madre mía, es un lío tremendo explicar esto sin una pizarra.

    Voy a explicar primero que forma tiene la función, sin demostrarlo. Así, con una idea visual de a qué quiero llegar, será más fácil cuando vaya demostrando cada detalle.

    Para construir una función cualquiera que cumpla el enunciado, podemos hacerlo así:

    1. Primero elegimos los valores que va a tomar la función, ordenados de menor a mayor, de modo que cada uno sea un divisor del siguiente. Salvo los dos últimos, que pueden coincidir, los demás deben ser diferentes. Por ejemplo, usaré los números: 2 6 12 48 y 96.

    2. Asignamos el último valor de la lista a f(0), y lo eliminamos de la lista.

    3. Asignamos el primer valor a f(1), si queremos, también se lo asginamos a f(2), si queremos, también a f(3), cuando nos aburramos de hacer esto, al siguiente valor de la función, le asignamos el segundo valor que hemos elegido. Por ejemplo:

    f(0) = 96
    f(1) = f(2) = f(3) = 2
    f(4) = 6

    4. Hecho esto, consideramos los valores asignados desde f(1) una secuencia, y la repetimos tantas veces como queramos, cuando nos aburramos de repetirla, sustituimos el último valor por el siguiente de nuestra lista. Por ejemplo:

    f(0) = 96
    f(1) = f(2) = f(3) = 2
    f(4) = 6
    f(5) = f(6) = f(7) = 2
    f(8) = 6
    f(9) = f(10) = f(11) = 2
    f(12) = 6
    f(13) = f(14) = f(15) = 2
    f(16) = 12

    5. Repetimos el paso anterior hasta usar todos los números de la lista, la función es periódica a partir de aquí. Por ejemplo:

    f(0) = 96
    f(1) = f(2) = f(3) = 2
    f(4) = 6
    f(5) = f(6) = f(7) = 2
    f(8) = 6
    f(9) = f(10) = f(11) = 2
    f(12) = 6
    f(13) = f(14) = f(15) = 2
    f(16) = 12
    f(17) = f(18) = f(19) = 2
    f(20) = 6
    f(21) = f(22) = f(23) = 2
    f(24) = 6
    f(25) = f(26) = f(27) = 2
    f(28) = 6
    f(29) = f(30) = f(31) = 2
    f(32) = 48
    Y para x>32: f(x) = f(x-32)

    Lo que demostraré es que cualquier función que cumpla que f(m-n) | f(m)-f(n), puede construirse así. Lo contrario también es cierto, pero no es necesario para resolver el problema así que me ahorraré esa parte (¡aunque es muy fácil!).

    Publica una respuesta
  15. Lo he intentado varias veces y está visto que no puedo demostrar esto sin una pizarra, así que voy a explicar los pasos que he seguido.

    Es una pena porque la demostración es relativamente sencilla (para ser el quinto problema de la IMO).

    Tengo que comenzar aclarando que hay un error en mi demostración de la periodicidad de la función. Concretamente, lo cometo cuando apresuradamente digo que la paridad de la función extiende la periodicidad al lado negativo de la función. Eso no es cierto porque la paridad también refleja toda la función con respecto al eje y, y por tanto los ciclos también estarían invertidos (en realidad no importa porque los ciclos son simétricos, pero eso no lo sé en este punto de la demostración).

    Este error es salvable fácilmete. En aquel mensaje, yo me limite a demostrarlo para el lado positivo, para así evitar encontrarme con ese punto singular en f(0), pero la misma demostración, simplemente teniendo cuidado con ese punto, demuestra la periodicidad para el lado negativo también.

    Paso 1.

    Aclarado esto, y llamando a al período de la función, y por tanto f(a) al valor más alto de la función excluyendo f(0), lo primero que hago es demostrar que si a partir de f(x) construyo otra función g(x), definida así:

    g(0) = f(a)
    g(x) = f(x)  \quad si \ x \neq 0

    Entonces esta nueva función también cumple que g(m)-g(n) = k g(m-n)

    Esto me permite estudiar esta nueva función, ya que todo lo que sea cierto para ella (en cuanto a la forma que debe tener), será cierto también para f(x), salvo en f(0). La nueva función es más fácil de analizar porque es periódica, y de período a, también en x=0.

    Paso 2.

    En el segundo paso, una vez me he deshecho de esa incómoda irregularidad en la periodicidad de la función, el valor máximo es g(a), y me pregunto qué sucede con el siguiente valor más alto, al que llamo g(b) (siendo b el valor positivo más bajo para el que la función toma este valor). Demuestro que b|a y que g(b)|g(a). Con un razonamiento muy parecido al que usé para demostrar que la función es casi periódica, de periodo a, y con una singularidad en f(0), demuestro también que la función también es casi periodica, esta vez con período b, salvo por las singularidades en g(ka).

    Paso 3.

    El tercer y úlltimo paso es el que nos podemos imaginar. Igual que antes me deshice de f(0), ahora me deshago de g(a). Demuestro que si a partir de g(x) obtengo otra función h(x), definida así:

    h(x) = g(b) \quad si \ a|x
    h(x) = g(x) Si a no divide a x (no sé como se pone esto en Latex)

    Entonces h(x) también cumple que h(m)-h(n) = k h(m-n)

    Así que puedo estudiar esta función en lugar de g(x)

    Pero esta función, a nuestros efectos, es exactamente igual g(x), sólo que el período es menor (b). Así que puedo repetir el segundo y tercer paso hasta que me quede con una función de período 1.

    Dado que cada vez que me deshago de una singularidad, resulta ser un múltiplo del valor por el que la sustituyo, el enunciado quedaría demostrado.

    No lo he demostrado aquí, solo he enumerado y explicado los pasos. Pero es casi mejor, si alguien tiene curiosidad por intentarlo siguiendo estos pasos, se lo pasará bien, y si tiene algún problema con alguno de estos pasos, aquí estaré para ayudar.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Hoy lunes os propongo el quinto problema de la IMO 2011 celebrada en Amsterdam…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *