L OME en Requena – Problema 4

Cuarto problema de la L Olimpiada Matemática Española celebrada en Requena los días 28 y 29 de marzo de 2014:

Sea (x_n) la sucesión de enteros positivos definida por

\begin{matrix}x_1=2 \\ x_{n+1}=2 x_n^3+x_n, \; \forall n \geq 2 \end{matrix}

Determinar la mayor potencia de 5 que divide al número x_{2014}^2+1.

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.

16 Comentarios

  1. Hola

    Deberías repasar las expresiones de Latex porque salen fatal y con el error “No formula provided”

    Publica una respuesta
  2. Es sencillo ver que como mínimo es 2014. lo que no veo tan claro es como mostrar que no es supoerior, que parece que no lo es.

    Es decir,

    (x_n)^2 + 1 = 0 (mod 5^n) (fácil)

    pero

    (x^n)^2 +1 =/=0 (mod 5^(n+1)) (no lo veo de momento)

    Saludos,

    Publica una respuesta
  3. Ignacio, yo estaba en un punto parecido, pero creo que lo he solventado. En definitiva, la mayor potencia de 5 que divide a (x_{2014})^2+1 [\latex] es precisamente 2014. El razonamiento es el siguiente:
    Trabajando en módulo 5 tenemos que:
    x_1=2 (mod 5) [\latex]
    x_2=2(2^3)+2=18=3 (mod 5) [\latex]
    x_3=2(3^3)+3=18=57=2 (mod 5) [\latex]
    Es decir, en módulo 5 la sucesión alterna los valores 2 y 3 indefinidamente de forma que:
    x_n= 2 (mod 5) [\latex] si n es impar y x_n=3 (mod 5) [\latex] si n es par.
    Y en cualquier caso un número de la forma (x_n)^2+1 [\latex] es múltiplo de 5 ya que:
    2^2+1=5=0 (mod 5) [\latex]
    2^3+1=10=0 (mod 5) [\latex]
    Por otra parte, se comprueba que cada número (x_{n+1})^2+1 [\latex] es múltiplo del anterior (x_n)^2+1 [\latex] de la siguiente manera:
    (x_{n+1})^2+1=(2(x_n)^3+x_n)^2+1=4(x_n)^6+(x_n)^2+4(x_n)^4+1=((x_n)^2+1)(1+4(x_n)^4) [\latex]
    Además se tiene que 1+4(x_n)^4 [\latex]también es múltiplo de 5 ya que:
    1+4(2^4)=0 (mod 5) [\latex]
    1+4(3^4)=0 (mod 5) [\latex]
    Ahora bien, si comprobamos que 1+4(x_n)^4 [\latex] es múltiplo de 5 una única vez para cualquier x_n entonces el número (x_{n+1})^2+1 [\latex] será exactamente n+1 veces múltiplo de 5, ya que lo hemos expresado de forma recursiva y (x_1)^2+1=5 [\latex].
    Basta con comprobar que 1+4(x_n)^4\neq 0 (mod 25) [\latex]. Para ello vemos que la sucesión módulo 25 es de la forma 2,18,7,18,7,…. alternádose los términos 7 y 8 indefinidamente. Y para 2, 7 y 18 la expresión 1+4(x_n)^4\neq 0 (mod 25) [\latex].
    Es decir, la mayor potencia de 5 que divide a (x_n)^2+1 [\latex] es precisamente n.

    Publica una respuesta
  4. Debe haber algún error con Latex… espero que igualmente se entienda. Saludos!

    Publica una respuesta
  5. Yo lo enfoqué por inducción, donde la hipótesis es que x{n}^2+1 es divisible por 5^n y no por 5^(n+1). La premisa es evidente para n=1 y en el caso general simplemente x{n+1}^2+1=4x{n}^6+x{n}^2+4x{n}^4+1=

    Por inducción se tiene:

    (5^n)k+4x{n}^4(5^n)k donde k es coprimo con 5.

    y esa expresión es (5^n)k(1+4x{n}^4) que se comprueba que los restos posibles en modulo 5 es solo el 0 y que en modulo 25 no hay ninguna posibilidad de ser cero (eso se hace estudiando el comportamiento de los restos de x{n} hasta establecer un ciclo).

    Publica una respuesta
  6. Probaremos por inducción que x_n^2+1=K \cdot 5^n donde K no es múltiplo de 5.

    Para n=1 y n=2 es simple comprobación.
    Supongamos que es cierto para un valor n>1:
    x_{n+1}^2+1=(2x_n^3+x_n)^2+1=4x_n^6+4x_n^4+x_n^2+1=4x_n^4(x_n^2+1)+x_n^2+1=
    =(4x_n^4+1)(x_n^2+1)
    Por la hipótesis de inducción:
    x_n^2+1=K \cdot 5^n \Rightarrow x_n^2=K \cdot 5^n -1 \Rightarrow 4x_n^4+1=4(K \cdot 5^n -1)^2+1=
    =4(K^2 5^{2n}-2K \cdot 5^n +1)+1=4K^2 5^{2n}-8K \cdot 5^n +5=5M
    donde M=4K^2 5^{2n-1}-8K \cdot 5^{n-1} +1=5^{n-1}(4K^2 5^n-8K )+1, que no es múltiplo de 5, ya que es múltiplo de 5 más uno
    Entonces:
    x_{n+1}^2+1=(4x_n^4+1)(x_n^2+1)5M \cdot K \cdot 5^n=MK \cdot 5^{n+1}

    Por inducción queda demostrado el resultado y la solución del problema es 2014

    Publica una respuesta
  7. Vuelvo a poner el comentario que hice ayer pero con las fórmulas de latex bien insertadas:

    Ignacio, yo estaba en un punto parecido, pero creo que lo he solventado. En definitiva, la mayor potencia de 5 que divide a x_{2014}^2+1 es precisamente 2014. El razonamiento es el siguiente:
    Trabajando en módulo 5 tenemos que:
    x_1=2 (mod 5)
    x_2=2\cdot2^3+2=18=3 (mod 5)
    x_3=2\cdot3^3+3=18=57=2 (mod 5)
    Es decir, en módulo 5 la sucesión alterna los valores 2 y 3 indefinidamente de forma que:
    x_n= 2 (mod 5) si n es impar y x_n=3 (mod 5) si n es par.
    Y en cualquier caso un número de la forma x_n^2+1 es múltiplo de 5 ya que:
    2^2+1=5=0 (mod 5)
    2^3+1=10=0 (mod 5)
    Por otra parte, se comprueba que cada número x_{n+1}^2+1 es múltiplo del anterior x_n^2+1 de la siguiente manera:
    x_{n+1}^2+1=(2x_n^3+x_n)^2+1=4x_n^6+x_n^2+4x_n^4+1=(x_n^2+1)(1+4x_n^4)
    Además se tiene que 1+4x_n^4 también es múltiplo de 5 ya que:
    1+4\cdot2^4=0 (mod  5)
    1+4\cdot3^4=0 (mod  5)
    Ahora bien, si comprobamos que 1+4x_n^4 es múltiplo de 5 una única vez para cualquier x_n entonces el número x_{n+1}^2+1 será exactamente n+1 veces múltiplo de 5, ya que lo hemos expresado de forma recursiva y x_1^2+1=5 .
    Basta con comprobar que 1+4x_n^4\neq 0 (mod 25) . Para ello vemos que la sucesión módulo 25 es de la forma 2,18,7,18,7,…. alternándose los términos 7 y 8 indefinidamente. Y para 2, 7 y 18 la expresión 1+4x_n^4\neq 0 (mod 25) .
    Es decir, la mayor potencia de 5 que divide a x_n^2+1 es precisamente n.

    Publica una respuesta
  8. Yo soy ingeniero, de esto de teoría de números sé solamente lo fundamental. Entendí bien la demostración por inducción que hizo Agustín, pero lo de MarcoTac aún no lo entiendo bien. ¿Cómo sospecharon que lo que había que demostrar era que x_n^2+1=K cdot 5^n ? Yo hubiera puesto 5^x o algo así…

    Agradecería mucho una aclaración. Soy curioso…..¡saludos!!!

    Publica una respuesta
  9. Perdón, no hallo cómo poner la multiplicación. Donce dice cdot debe ir el punto de la multiplicación.

    Publica una respuesta
  10. Hola Omar, yo también soy ingeniero! La clave está en fijarse que x_{n+1}^2+1=(x_n^2+1)(4x_n^4+1) . Y observar que x_1^2+1=5 y 4x_1^4+1=65=5\cdot13 , de lo que ya deduces que x_2^2+1 es mútiplo de 5^2 . Otra observación importante es ver que x_n^2+1 y 4x_n^4+1 son ambos múltiplo de 5 para cualquier x_n . Para ver esto trabaje en módulo 5 (restos de dividir por 5). Para el caso de x_n^2+1 ya no era necesario al ser múltiplo de “los anteriores” y en concreto de x_1^2+1=5 , pero en mi caso esto lo observé a priori, sin necesidad de poner x_n^2+1 en función de “los anteriores”. Llegados aquí te preguntas ¿que pasa con x_3^2+1 ?, como x_3^2+1=(x_2^2+1)(4x_2^4+1) será múltiplo al menos de 5^3 ya que el primer término es múltiplo de 5^2 y el segúndo al menos de 5 (y si fuese múltiplo un única vez de 5 entonces x_3^2+1 sería múltiplo de 5^3 y no de 5^4 ). Es decir, si 4x_n^4+1 fuese siempre múltiplo de 5 una única vez (múltiplo de 5 y no de 5^2 ) independientemente de n… ¡ya está!
    Por otra parte, para poner el símbolo de multiplicar es \cdot.

    Publica una respuesta
  11. Gracias. Si, lo entendí bien. Leí que este ejercicio es de unas olimpiadas para gente de bachillerato. Entiendo que son 6 problemas, y este parece ser de dificultad intermedia entre los seis. Me gustaría saber si alguno de los ganadores de medallas los resolvió todos satisfactoriamente en cuatro horas, y cuál fue el nivel de logro de los mejores participantes (información que, me parece, no figura en la página). Yo me imagino que si alguien resolvió correctamente los seis en cuatro horas , con 14-19 años de edad, debe ser un genio o poco menos. Creo que yo no habría podido resolver nada o casi nada. No sé para qué uno, que es normal, estudia tanto si hay gente que puede hacer todo lo que uno hace o hará en la vida sin estudiar casi nada.

    En cuanto al punto de la multiplicación, puse el código, pero no funcionó bien. Nunca he usado Latex, copié lo que hacían los demás en sus comentarios.

    Saludos desde Chile.

    Publica una respuesta
  12. Hasta donde yo sé nunca se ha alcanzado la puntuación perfecta en la OME. La vez que estuvo más cerca fue hace 4 años con 39 de 42 puntos posibles (al menos ese fue el mejor resultado desde que se puntua sobre 42, que lleva siendo así 25 años (y quizá desde sus orígenes hace 50 años)).

    En cuanto a las horas, se dan tres horas y media para resolver los tres primeros y tres horas y media para los siguientes.

    Volviendo a lo anterior, es muy complicado puntuar perfecto en todo pues siempre habrá algo que no se sepa o que tengas un pequeño traspiés de un par de puntos. Al fin y al cabo están pensados para calibrar a todo el mundo y los 6 problemas deben ir desde algunos que sean asequibles para casi todos hasta alguno muy difícil de resolver.

    Publica una respuesta
  13. Omar, el punto lo puedes poner con “\cdot” (sin las comillas).

    Y ya aprovecho para volver a comentar lo de la edición de los comentarios: si editáis algún comentario vuestro que tenga código LaTeX tenéis que escribir cada contrabarra dos veces, porque el plugin de edición de comentarios se “come” una en cada fórmula (sigo sin saber por qué ocurre eso). Es decir, si tienes escrito \cdot y editas el comentario deberás escribir al editarlo \\cdot, para que el plugin se coma una de ellas y deje la otra.

    Saludos.

    Publica una respuesta
  14. Omar, la clave de los buenos resultados en las olimpiadas es el entrenamiento. China obtiene mejores resultados porque entrena más y no porque haya más genios chinos. Yo diría que un alumno de bachillerato que sólo haya recibido los contenidos del bachillerato y no haya entrenado resuelve correctamente todos los problemas entonces sí diría que es un genio.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Cuarto problema de la L Olimpiada Matemática Española celebrada en Requena los días 28…

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 *