La misteriosa sucesión de Kolakoski

Matemoción

William Kolakoski (1944-1997) fue un artista que se dedicó también a la matemática recreativa. Es conocido –fuera del ámbito artístico– por la sucesión que lleva su nombre y que él mismo introdujo en 1965 en la revista American Mathematical Monthly:

Imagen 1: Captura de pantalla del problema planteado en la referencia [1].

El matemático Rufus Oldenburger ya había descrito esta sucesión en 1939, aunque parece en ese momento no llamó la atención de la comunidad científica.

En este ‘problema 5304’ planteado en la American Mathematical Monthly, Kolakoski escribía los primeros términos de la sucesión, proponía describir una regla para construirla, encontrar su n-ésimo término y decidir si se trata de una sucesión periódica.

Para describirla se puede recurrir a la llamada ‘sucesión contadora’ de una dada, es decir, la sucesión formada por aquellos enteros positivos que indican el número de bloques de símbolos consecutivos iguales en la sucesión. Por ejemplo, la sucesión contadora de:

a, b, b, a, a, b, b, b, a, b, a, a, b, b,…,

es 1, 2, 2, 3, 1, 1, 2, 2…; porque el término a aparece una vez, la b dos veces, la a dos veces, la b tres veces, la a una vez, la b una vez, la a dos veces, la b dos veces,…

La sucesión de Kolakoski posee bloques de uno o dos dígitos de ‘1’ y ‘2’; los primeros son:

1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1,…

Su sucesión contadora es:

1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2,…,

ya que los bloques de dígitos van agrupados de la siguiente manera:

1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1,…

Es decir, la sucesión contadora de la de Kolakoski… ¡vuelve a ser la de Kolakoski!

Cada término de la sucesión de Kolakoski genera un ‘camino’ de uno o dos términos ‘futuros’. ¿Cómo? El primer 1 de la sucesión genera un camino de “1”, es decir, a sí mismo. El primer 2 genera el camino “2, 2” (que se incluye a sí mismo) y el segundo 2 genera un camino “1, 1” y así sucesivamente.

Construcción de la sucesión de Kolakoski. Fuente Wikimedia Commons.

En [5] se demuestra que la sucesión de Kolakoski no es periódica. En [6] el autor proporciona una fórmula recursiva para la sucesión… Pero muchos otros problemas relativos a esta sucesión quedan aún abiertos, como los siguientes:

  • dada una cadena de dígitos en la sucesión, ¿vuelve a aparecer en algún otro lugar de la sucesión?

  • dada una cadena de dígitos en la sucesión, ¿la cadena inversa también aparece en algún otro lugar de la sucesión?

  • ¿aparecen los dígitos 1 y 2 con la misma frecuencia en la sucesión de Kolakoski?

En este video del canal de YouTube de Numberphile, el divulgador Alex Bellos explica algunas de las curiosidades sobre la misteriosa sucesión de Kolakoski…

Existen numerosas variaciones –incorporando más cifras a la sucesión, o cifras diferentes, etc. (ver [4])– que añaden dificultad al tema y hacen surgir otro tipo de preguntas, muchas de ellas aún sin solución. Así avanzan las matemáticas… aumentando la dificultad de los retos y buscando nuevas ideas y diferentes técnicas que puedan ayudar a resolverlos.

Referencias

[1] William Kolakoski (1965). Problem 5304, The American Mathematical Monthly 72: 674.

[2] The Kolakoski Sequence, Futility Closet, 5 octubre 2018

[3] N. J. A. Sloane, A000002 Kolakoski sequence, The On-Line Encyclopedia of Integer Sequences (y los 10 500 primeros términos de la sucesión).

[4] Kolakoski Sequence, Wikipedia (consultado: 6 octubre 2018)

[5] Necdet Üçoluk (1966). Problem 5304, The American Mathematical Monthly 73, 681-682.

[6] Steinsky, Bertran (2006). A recursive formula for the Kolakoski sequence A000002. Journal of Integer Sequences. 9 (3).

Sobre la autora: Marta Macho Stadler es profesora de Topología en el Departamento de Matemáticas de la UPV/EHU, y colaboradora asidua en ZTFNews, el blog de la Facultad de Ciencia y Tecnología de esta universidad.

3 comentarios

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *