Solución del problema de marzo del 2006

 

Juan escribe un número con 2187 dígitos en el pizarrón, cada dígito un 1 o un 2. Judith crea un nuevo número, a partir del de Juan, leyendo de izquierda a derecha y reemplazando cada 1 por 112 y cada 2 por 111 (por ejemplo, si el número de Juan empieza con 2112, el de Judith empieza con 111112112111).

Cuando Judith termina de escribir su número, nota que los primeros 2187 dígitos empezando de la izquierda en su número y el de Juan son los mismos. Cuántas veces ocurren 5 unos consecutivos en el número de Juan?

            Recibimos soluciones correctas de

Vincent Bardoux (Francia)

Wolfgang Kais (Alemania)

Mohamed Benchaib (Marruecos)

Karim Laaouini (Marruecos)

Pierre Bornsztein (Francia)

Normand LaLiberté (Ontario)

Bernard Carpentier (Francia)

Matthew Lim (internet)

K.A. Chandrashekara Juan Mir Pieras (España)
Philippe Fondanaiche (Francia) Mark Pilloff (USA)
Xavier Hecquet (Francia) A. Teitelman (Israel)
LeCarré de l'Hypoténuse (Francia) Said Amghibech (internet)

Solución.

Hay 182 cadenas de 5 unos consecutivos en el número de Juan. 

            La mayoría de las soluciones llegaron a esta conclusión mediante una cadena similar de observaciones simples.

Observación 1.  La sucesión de Judith tiene que comenzar con 111 o 112; como sus dígitos iniciales son los mismos que los de Juan, vemos que tanto el número de Juan como el de Judith tienen que comenzar con 1 (leyendo de izquierda a derecha). 

Observación 2.  El número de Juan está completamente determinado: como su primer dígito es 1, los tres primeros dígitos de Judith son 112. Como estos son también los tres primeros de Juan, el número de Judith tiene que comenzar con

112 112 111

(una vez que Judith reemplaza los números 1, 1, y 2). Continuamos con el proceso en etapas: Judith reemplaza los primeros 3k dígitos del número de Juan para obtener los primeros 3k+1 dígitos de su número, que luego serán los primeros 3k+1 dígitos del número de Juan.

Observación 3. Las reglas implican que el número de 2 en la etapa k+1es igual al número de 1 en la etapa k. Además, nunca puede haber dos 2 consecutivos, porque cualquier 2 aparece al final de un triplete, para ser seguido por otro triplete que empieza con 11. Una cadena de cinco 1s consecutivos en la etapa 3k+1 viene entonces de una secuencia 21 en la etapa 3k. Se sigue que el número de estas 5-cadenas (las que queremos contar) el igual al número de pares 21 en la etapa previa.

            Ahora el proceso está claro: en cada etapa contamos el número de 1s y 2s; esto nos da el número de 2s y de 5-cadenas, respectivamente, en la etapa siguiente. Casi. Hay un pequeño detalle técnico: si el dígito 2 aparece al final de la sucesión en la etapa k, la sucesión en la etapa k+1comienza con un bloque de tres 1, no cinco. Entonces el número de 5-cadenas en cada etapa es igual a uno menos que el número de 2 en la etapa anterior si esa etapa termina con 2. Para ser más precisos, la regla de generación establece que el dígito final de una etapa impar es 1, y en una etapa par es 2. De manera que el número de 5-cadenas en las etapas 1, 3, 5, 7 es igual al número de 2 en las etapas 0, 2, 4, y 6; el número de 5-cadenas en las etapas 2, 4 y 6 es igual a uno menos que el número de 2 en la etapa previa.

            En la tabla siguiente 3k es el número de dígitos considerados en el número de Juan en la etapa k. El número de 1 es el número de dígitos en esa etapa menos el número de 1 en la etapa anterior; esto es porque el número de 2 en la sucesión es igual al número de 1 en la etapa anterior. El número de 5-cadenas es esencialmente igual al número de 2 en la etapa previa. La pregunta es cuál es dicho número en la etapa 7, que la tabla muestra es 182.

Etapa

# dígitos observado

#1s

#2s

#5-cadenas

0

1

1

0

0

1

3

3 – 1 = 2

1

0

2

32 = 9

9 – 2 = 7

2

1 – 1

3

33 = 27

27 – 7 = 20

7

2

4

34 = 81

81 – 20 = 61

20

7 – 1

5

35 = 243

243 – 61 = 182

61

20

6

36 = 729

(547)

182

61 – 1

7

37 = 2187

(1640)

(547)

182

Comentarios.

            Muchos de nuestros lectores encontraron el problema fascinante. Notaron que la regla para generar la sucesión permite que el proceso continúe indefinidamente, de manera que proveyeron un análisis del número de 1 y 2 en la etapa 3n para todo n > 0.  El número de 1 es, para la tercera columna de nuestra tabla,

para n par,

para n impar.

Entonces los primeros 3n dígitos de la sucesión serán  unos y   dos. Por ejemplo, cuando n = 5 — impar — hay (36– 1)/4 = 728/4 = 182 unos. En consecuencia, hay 182 dos entre los primeros 36 = 729 dígitos, y (ya que 6 es par) el dígito 729 es un 2, lo que confirma que el número de 5-cadenas entre los primeros 37  = 2187 dígitos es en efecto 182.

            La regla para rescribir la sucesión de Juan tiene una interesante consecuencia. Si en la etapa k denotamos con A y B los bloques inicial y final de 3k-1 dígitos, entonces la cadena de 3k dígitos tiene la forma AAB, mientras que la etapa siguiente tiene la forma AAB AAB AAA (similar a como fuimos de 112 a 112 112 111).  Además, como hemos visto, el número de 2 en cada etapa difiere en 1 de ¼ de los dígitos. Aunque la sucesión sigue un patrón tan regular, Mir ha observado que la sucesión infinita no es periódica: si una cadena de p dígitos comienza en el dígito d y termina en 1, la cadena correspondiente en la nueva sucesión (de 3p dígitos comenzando en el dígito 3d) termina en 2, y recíprocamente, si termina en 2 la sucesión rescrita termina en 1. Mir se preguntó si habrá reglas simples para rescribir las sucesiones que 1 y 2 que conduzcan a sucesiones infinitas periódicas. Entre varios ejemplos, sugiere reemplazar 1 por 121, y 2 por 212.

            Para terminar, Hecquet nos ha provisto del número de Juan para beneficio de aquellos interesados en ver los 2187 dígitos.

El número de Juan:

112112111112112111112112112112112111112112111112112112112112111112112111112 112111112112111112112111112112112112112111112112111112112112112112111112112 111112112111112112111112112111112112112112112111112112111112112112112112111 112112111112112112112112111112112111112112112112112111112112111112112112112 112111112112111112112111112112111112112111112112112112112111112112111112112 112112112111112112111112112111112112111112112111112112112112112111112112111 112112112112112111112112111112112112112112111112112111112112112112112111112 112111112112112112112111112112111112112111112112111112112111112112112112112 111112112111112112112112112111112112111112112111112112111112112111112112112 112112111112112111112112112112112111112112111112112111112112111112112111112 112112112112111112112111112112112112112111112112111112112111112112111112112 111112112112112112111112112111112112112112112111112112111112112111112112111 112112111112112112112112111112112111112112112112112111112112111112112112112 112111112112111112112112112112111112112111112112112112112111112112111112112 111112112111112112111112112112112112111112112111112112112112112111112112111 112112111112112111112112111112112112112112111112112111112112112112112111112 112111112112112112112111112112111112112112112112111112112111112112112112112 111112112111112112111112112111112112111112112112112112111112112111112112112 112112111112112111112112111112112111112112111112112112112112111112112111112 112112112112111112112111112112111112112111112112111112112112112112111112112 111112112112112112111112112111112112111112112111112112111112112112112112111 112112111112112112112112111112112111112112111112112111112112111112112112112 112111112112111112112112112112111112112111112112112112112111112112111112112 112112112111112112111112112112112112111112112111112112111112112111112112111 112112112112112111112112111112112112112112111112112111112112111112112111112 112111112112112112112111112112111112112112112112111112112111112112112112112 111112112111112112112112112111112112111112112112112112111112112111112112111 112112111112112111112112112112112111112112111112112112112112111112112111112 112111112112111112112111112112112112112111112112111112112112112112111112112 111112112112