Una sucesión de dígitos $1$ y $2$ está determinada por las siguientes dos propiedades:
(i) La sucesión se construye escribiendo, en algún orden, bloques $12$ y bloques $112$.
(ii) Si se reemplaza cada bloque $12$ por $1$ y cada bloque $112$ por $2$ se obtiene, de nuevo, la misma sucesión.
¿En qué posición está el centésimo dígito $1$? ¿Cuál es el milésimo dígito de la sucesión?
Como a raíz de la sucesión se debe poder crear otra que sea igual reemplazando los 12 por 1 y los 112 por 2, veamos que no es posible que la sucesión comience por un bloque 112:
1 1 2 ...
Se transforma en:
2 ...
Como 1 ≠ 2, entonces el primer bloque no puede ser 112.
Veamos como se construye una cierta cantidad de la sucesión siguiendo las propiedades (para mayor comodidad en la escritura e interpretación la escribiré sin comas, y dejando un espacio entre los bloques):
Vemos que a partir de esta segunda sucesión, se puede crear otra igual (tercera sucesión) siguiendo las propiedades de la primera sucesión:
12 112 12 12 112 ...
Podremos crear una cuarta con esta tercera:
12 112 ...
Y una quinta con la cuarta:
12 ...
Vemos que se pueden formar infinitas sucesiones iguales a partir de la primera siguiendo las propiedades.
Estas sucesiones que escribimos anteriormente nos servirán para contar más facilmente la cantidad de unos de la primera, y nos permitirán hallar su milesimo término.
Para formar un 12 en la cuarta sucesión se necesitan de 17 unos y 12 dos de la primera sucesión. Para formar un 112, 24 unos y 17 dos.
Como la cuarta sucesión es igual a la primera, entonces podemos escribirla, y contar cuantos unos le cuesta a la primera hacer la cuarta:
12 112 12 12 112| 12 ...
17+24+17+17+24=99 |+17
Entonces el centésimo uno es el primer uno del cuarto doce.
Veamos cuantos números hay hasta esa posición incluida:
Un doce de la cuarta sucesión está formado por 29 números de la primera, y un 112 por 41.
3*29 + 2*41 + 1 = 170
En la quinta sucesión, un uno está compuesto por 29 números de la primera, y un 2 por 41. Por lo tanto un 12 está conformado por 70 números (21 + 49) y un 112 por 99 (21*2 + 49).
Sumemos:
12 112 12 12 112 12 112 12 112 12 12 112| 12 ...
70+99+70+70+99+70+99+70+99+70+70+99 =
= 70*7 + 99*5 = 985
El milésimo término es el 15vo número dentro de un 12 de la quinta sucesión.
Contando nos damos cuenta de que es un 1.
Respuestas:
El centésimo 1 está en la posición 170.
El milésimo dígito es un 1.
Sabemos que la sucesión debe empezar con un bloque $12$, ya que si empezara con un $112$ el primer dígito luego de reemplazar sería un $2$ y por lo tanto sería una sucesión diferente.
Ya que el primer bloque es $12$, el segundo debe ser $112$ para que luego de reemplazar quede $12$. Podemos aplicar esta lógica múltiples veces para construir la sucesión infinita.
Siendo $a_0$ la sucesión $1;2$ (o simplemente $12$), $a_n$ es la sucesión resultante después de reemplazar los $1$s por bloques $12$ y los $2$s por $112$ en la sucesión $a_{n-1}$.
Llamemos $u_n$ a la cantidad de $1$s en $a_n$ y $d_n$ a la cantidad de $2$s en $a_n$.
Por cada $1$ en $a_n$ tenemos un $1$ y un $2$ en $a_{n+1}$ y, por cada $2$, un $2$ y dos $1$s, por lo tanto $u_n=u_{n-1}+2d_{n-1}$ y $d_n=u_{n-1}+d_{n-1}$. Con estas fórmulas, llegamos a que $a_7$ tiene 985 dígitos, por lo que hay que averiguar cuales son los 15 que faltan para llegar a 1000. Para ello, es útil saber los últimos 15 dígitos de esta sucesión.
Teniendo en cuenta que todas las sucesiones terminan en $2$ (ya que todas estan hechas de bloques $12$ y $112$), sabemos que todas a partir de $a_1$ terminan en $112$, y eso implica que $a_2$ termina en $1212112$, por lo que todas las que siguen terminan en $1212112$ tambien, y así sabemos que $a_3$ (y todas las que le siguen) terminan en $12 112 12 112 12 12 112$ (que son 15 dígitos).
Sabiendo esto y que un bloque $112$ no puede ser seguido por otro bloque $112$ (ya que en el reemplazo serían dos $2$ seguidos), continuamos la sucesión desde el final de $a_7$. Si hacemos dos reemplazos, los últimos 15 dígitos de $a_7$ se reducirían a $112$, y como luego de un $112$ no puede seguir otro $112$, ponemos un $12$ y lo expandimos dos veces para obtener $12 112 12 12 112$. Ahi tenemos 12 dígitos, solo faltan 3 para los 1000. ya que termina en $112$, ponemos un $12$ y llegamos a los 999 dígitos, por lo que el primer dígito del siguiente bloque es el dígito 1000, y como ambos bloques empiezan por $1$, el dígito 1000 es un $1$.
Para sacar la posición del centésimo $1$, podemos obtener gracias a la fórmula de $u_n$ que en la sucesión $a_5$ hay 99 $1$s. Debido a esto, el siguiente dígito $1$ es el centésimo, y usando las fórmulas de $u_n$ y $d_n$ obtenemos que en $a_5$ hay 169 dígitos, y como el próximo dígito es un $1$ ya que es el primer dígito de un bloque (y todos los bloques empiezan por $1$) entonces el centésimo $1$ está en la posición 170.
