Desafíos GaussianosyGuijarro – Desafío nº9: “Una sucesión muy particular” – Solución y ganador

Unos días después de terminar el plazo para el envío de respuestas os traigo la solución del Desafíos GaussianosyGuijarro – Desafío nº 9: Una sucesión muy particular y, por tanto, del ganador de El número en la Naturaleza. Matemáticas y comprensión de la realidad observable, 1.

Se han recibido 45 respuestas, de las cuales 16 eran correctas. A continuación recordamos el enunciado del problema y dejamos la solución de Antonio Rojas, que fue quien nos lo propuso:

Definimos la siguiente sucesión de números enteros, a(n), de forma recurrente:

\begin{matrix} a(1)=1 \\ \\ a(n)=\begin{cases} -a(n/2), & \mbox{ si } n \mbox{ es par} \\ 1+a(n-1), & \mbox{ si } n \mbox{ es impar} \end{cases} \end{matrix}

Este noveno desafío consiste en responder correctamente a estas dos cuestiones:

1) Demostrar que para todo número entero k existen infinitos números enteros positivos n tales que a(n)=k.

2) Hallar el menor entero positivo n tal que a(n)=1000.


La solución propuesta por Antonio es la siguiente:

La definición por recurrencia de la sucesión sugiere que se intente demostrar por inducción y, de hecho, muchas de las respuestas obtenidas intentan resolverlo así­. Sin embargo, en este caso es mucho más directo razonar en base 2. Sabemos que todo número entero positivo n puede escribirse de manera única en base 2, es decir, en la forma

n=c_m \cdot 2^m+c_{m-1} \cdot 2^{m-1}+ \cdots+c_2 \cdot 2^2+c_1 \cdot 2^1+c_0

donde m\geq 0, c_m=1 y c_i=0 ó 1 para todo i=0,\ldots,m-1. Teniendo en cuenta que a(n+c)=a(n)+c si n es par y c=0 ó 1 (lo cual es evidente si c=0 y por definición de la sucesión a(n) si c=1) tenemos que

\begin{matrix} a(n)=a(c_m\cdot 2^m+c_{m-1}\cdot 2^{m-1}+\cdots+c_2\cdot 2^2+c_1\cdot 2^1+c_0)= \\ =a(c_m\cdot 2^m+c_{m-1}\cdot 2^{m-1}+\cdots+c_2\cdot 2^2+c_1\cdot 2^1)+c_0= \\ =a(2(c_m\cdot 2^{m-1}+c_{m-1}\cdot 2^{m-2}+\cdots+c_2\cdot 2+c_1))+c_0= \\ =-a(c_m\cdot 2^{m-1}+c_{m-1}\cdot 2^{m-2}+\cdots+c_2\cdot 2+c_1)+c_0= \\ =-a(c_m\cdot 2^{m-1}+c_{m-1}\cdot 2^{m-2}+\cdots+c_2\cdot 2)-c_1+c_0= \\ =a(c_m\cdot 2^{m-2}+c_{m-1}\cdot 2^{m-3}+\cdots+c_2)-c_1+c_0= \\ =\cdots=c_0-c_1+c_2-c_3+\cdots+(-1)^m\cdot c_m, \end{matrix}

es decir, a(n) no es más que la suma alternada de las cifras de n en base 2 o, dicho de otra forma, el número de unos en posición impar menos el número de unos en posición par (empezando a contar desde la última cifra).

A partir de aquí­ es fácil responder a las preguntas planteadas:

  • para cada entero k existen infinitos n tales que a(n)=k: basta tomar como n cualquier número que en base 2 tenga la forma 1010101 \ldots 101 (con k unos) seguido de un número par de ceros si k es positivo, la forma 1010101 \ldots 101 (con -k unos) seguido de un número impar de ceros si k es negativo, o 11 seguido de un número par de ceros si k=0.
  • También se deduce que el menor n tal que a(n)=1000 debe tener, como mínimo, 1999 cifras en base 2 (puesto que debe tener al menos 1000 unos en posición impar), y el único con 1999 cifras que lo cumple es el que no tiene ningún uno en posición par, es decir, el número

    1+2^2+2^4+2^6+\cdots+2^{1998}=1+4+4^2+4^3+\cdots+4^{999}=(4^{1000}-1)/3

    que tiene 602 cifras en base 10.

Comentarios sobre las soluciones

Básicamente se han recibido dos tipos de soluciones:

  • Por un lado las que usan un argumento parecido al anterior, posiblemente con alguna variación (como usar base 4 en vez de base 2). De entre ellas destacamos las de José Antonio Prado Bassas (@eliatron), Massimo Milesi, José Antonio Rama López y Romeo.
  • Por otra parte están las soluciones por inducción: algunas de éstas son incompletas, pues aunque se llega al resultado correcto para el menor n tal que a(n)=1000, no se demuestra que ése es en efecto el menor. De entre las correctas destacamos las de Felix Gimeno y Enric Tamarit.
  • Y para finalizar destacar especialmente la solución de Miguel Capitán Ruiz quien, además de resolver el problema de las dos formas, con tablas numéricas incluidas, nos ofrece un entretenido relato detectivesco.

Y el ganador de este desafío ha sido, curiosamente, el propio Miguel Capitán Ruiz (los sorteos son así de caprichosos), que pronto recibirá El número en la Naturaleza. Matemáticas y comprensión de la realidad observable, 1. Enhorabuena.

Muchas gracias a todos por participar.

En pocos días habrá nuevo desafío, el décimo. Estad atentos.

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. Pues ahora que lo pienso no se si estaré entre los acertantes, supongo que sí, ya que mi metodo calculaba la forma de obtener cada número natural (el primero de forma implicita).

    Lo cierto es que no me preocupé en absoluto en demostrar que para a(n)=1000, el valor de ‘n’ obtenido era el menor. Aunque creo que quedó implicito, yo entiendo que el segundo punto pide “Hallar el valor”, y no pide “Demostrar”.

    Tal vez sólo sea un problema mío, y no se si lo compartis los demás. Pero para futuros problemas me gustaría aclararlo antes. Aunque ahora que lo pienso creo que lo mejor será demostrarlo todo siempre 🙂

    Por cierto, tal y como se deduce de la solución expuesta, y como dije en mis comentarios al problema la solución a la segunda pregunta consiste en el valor 111…111 (400 unos) en base 4.

    Publica una respuesta
  2. Por un poco más se podía haber puesto la lista de respuestas consideradas acertadas, 8-9 nombres más, y así uno sabe si dio o no; porque el índice de aciertos ha sido muy bajo.
    También pienso que no se pedía demostrar.

    Publica una respuesta
  3. En realidad decía “hallar el mínimo n tal que a(n) = 1000”. Pero ¿cómo estamos seguros de que el n que hallamos es el mínimo? Para ello hay que demostrar que es el mínimo. Al menos yo lo entendí así.
    Mira que fácil lo hizo Antonio Rojas y yo me reventé la cabeza dándole vueltas al asunto. Por eso algunos son genios y otros sólo admiramos de lejos.

    Y la mía esta destacada porque salió bien todo, o porque estuvo dentro de intentos parecidos a la de Rojas.

    Publica una respuesta
  4. Yo no sé si lo hice bien o mal (el planteamiento seguro que es correcto, pero algun error se puede escapar en el intermedio) pero el nº lo obtuve de manera constructiva, por lo que era el menor sin duda.

    Publica una respuesta
  5. Romeo, te dejo mi solución si te interesa. Creo que Diamond ya tiene bastante en mantener la página para publicar todas las respuestas. Además no se como las mandais vosotros, pero yo lo hice en word, y eso no se traslada directamente a texto plano o a latex para pegarlo aquí fácilmente.

    Esta bien comentarlas las soluciones, por un lado se aprende de los errores y por otro se descubren otros puntos de vista.

    Saludos

    1. Dado un a(n) = k se tiene que todo término de la forma a(4cn) = k, siendo c un número natural (me parece trivial, no es necesario demostrarlo, pero si hubiera que hacerlo se ve fácilmente por inducción. Es cierto para 1, y si es cierto para c se cumple que lo es para c+1). Por tanto, existen infinitos números c tales que a(4cn) = k, para todo k.

    2. Todo término a(2n) = -a(n) => a(4n) = a(n)

    (a) Partiendo del primero término la secuencia de números naturales se obtiene mediante la aplicación de la ecuación n_{i+1} := 4n_{i+1}. Así se obtiene la primera aparición de cada número en la serie. Es decir: a(n=1) = 1, a(4n+1) = 5, …

    (b) De esa forma se obtiene que la secuencia de términos relacionados con los primeros números naturales serían: 1, 5, 21, 85, …, 4n_{i+1}

    (c) Es decir, consiste en multiplicar por 4 y sumar 1 al término anterior de forma sucesiva hasta llegar al 1000.

    (d) Si usamos la base 4 para representar a los números tendremos la secuencia: 1, 11, 111, 1111, … Multiplicar por 4 en base 4 es como multiplicar por 10 en decimal (es decir desplazar los dígitos a la izquierda y añadir un 0). Sumar un 1 en base 4 es igual que en decimal.

    (e) El término a(n) = 1000 se obtiene para n = 111…111 ( 1000 unos en base 4), es decir 4^{999} + 4^{998} + \dots + 4^2 + 4^1 + 4^0.
    Esta suma se puede evaluar como (4^{1000} – 1)/3
    No se que pasa con la formula de latex, que no sale bien por mucho que lo intento. El resultado es (4^1000 – 1) / 3.

    Publica una respuesta
  6. Yo también envié mi respuesta por Word, es más fácil manejar aquel editor de ecuaciones que el latex. Lástima que no se puedan colgar archivos en el blog. De todos modos sigue siendo muy bueno este lugar de encuentro. Siguen mis felicitaciones para aquellos que hacen que esto sea posible.

    Genial tu aporte de 4n+1, siendo n el término anterior en la sucesión de números enteros positivos. Ni cuenta me había dado de eso :(.
    Tampoco se me ocurrió nunca utilizar la base 4, ni la base 2.
    Yo en lugar de usar 4n+1, use la idea de que a(n)=a(n \times 2^{2i}) par ver que existen infinitos n para los que k = a(n).
    Luego probé que k = a{({4^k-1 \over 3})} y finalmente que {4^k-1 \over 3} es el mínimo n para el cual se verifica la igualdad.

    Publica una respuesta
  7. El tema de publicar las respuestas es algo de lo que se ha hablado ya por aquí en alguna ocasión. Os aseguro que a mí me encantaría poder publicar todas las respuestas correctas (y esencialmente distintas) que habéis enviado, pero por desgracia no tengo tiempo suficiente.

    Como bien dice Cartesiano Caótico, el mantenimiento del blog lleva su tiempo, y además las soluciones son enviadas de todas las formas que os podéis imaginar: en doc (con las fórmulas con el editor de ecuaciones o similar), en pdf (creado a partir de LaTeX), en un archivo de imagen (que muchas veces corresponde a una foto del problema escrito a mano)… El tiempo que debería invertir en adaptarlas para publicarlas en el blog es demasiado grande. Espero que me comprendáis.

    Publica una respuesta
  8. esta web es genial, yo estoy empezando mi proyecto web de matemáticas y la verdad que os visito muchas veces y estoy anotando ideas.
    un fuerte saludo.

    Publica una respuesta
  9. Por supuesto que se comprende gaussianos. Gran laburo el tuyo y gracias por hacerlo.

    Publica una respuesta
  10. Es una sugerencia. En este desafío me ha sorprendido el bajo porcentaje de aciertos.
    Creo que hubiera sido muy interesante hacer alguna mención genérica de los errores más habituales.
    Suelo aprender más de mis errores que de los aciertos de los demás.

    Publica una respuesta
  11. ¿Cómo puedo saber al menos si mi solución era correcta o no?

    Publica una respuesta
  12. julio, le pasé el otro día tu sugerencia a Antonio Rojas. Esperemos a que tenga un rato libre para ver si considera interesante contarnos algo.

    Fomlhaut, en principio prefiero no contestar individualmente a quienes enviáis soluciones, ya que ello conlleva mucho trabajo, no por contestar en sí, sino porque luego podría ser razonable que quien envió una respuesta incorrecta preguntara por las razones por las que no lo es, etc. Espero que lo comprendas. Muchas gracias.

    Publica una respuesta
  13. Quizá Fomlhaut hacía referencia a hacer un listado completo de los que respondieron bien, por descarte quienes no están allí no respodieron bien.

    Publica una respuesta
  14. julio: La mayor parte de las respuestas consideradas “no válidas” ha sido por incompletas, no por erróneas. El fallo más frecuente, con diferencia, es dar por supuesto sin justificación que la sucesión b(k+1)=4b(k)+1 nos da el menor índice tal que a(b(k))=k (teniendo en cuenta que la sucesión va oscilando entre valores positivos y negativos esto no es evidente). Otras respuestas olvidaban probar la parte (a) para valores negativos de k. Igual en un examen esto habría supuesto unas décimas menos, pero aquí no me parecía justo para los que sí lo han resuelto por completo el dar estas respuestas incompletas por válidas.

    Publica una respuesta
  15. Muchas gracias Antonio. Considero muy acertado tu criterio, es justo. Nada que reprochar. Soy de los que no argumentó debidamente el tema.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com -
    Información Bitacoras.com... Valora en Bitacoras.com: Unos días después de terminar el plazo para el envío de respuestas os traigo…
  2. Una preciosa solución para el noveno desafío GyG - Gaussianos | Gaussianos -
    [...] la solución que os traigo hoy para el noveno desafío GyG. La envió Miguel Capitán, que además resultó ser…

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 *