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.

Print Friendly, PDF & Email
0 0 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉