El teorema de Zeckendorf es un enunciado matemático muy productivo dentro de su modestia. Ha originado generalizaciones en distintas direcciones y también ha dado lugar a aplicaciones en diversos ámbitos como las propias Matemáticas, la tecnología o el arte. Veamos algunas de ellas como continuación del artículo precedente sobre el teorema de Zeckendorf No es brujería. ¡Son Matemáticas!.
“The Zeckendorf Game”
Comenzaremos con un ejemplo de aplicación del teorema en el campo de la teoría de juegos combinatorios, el “Zeckendorf Game”
El juego parte de una lista de una cantidad cualquiera de unos. Dos jugadores van haciendo alternativamente cambios en la lista con unas reglas basadas en la relación de recurrencia de la sucesión de Fibonacci, ya sea combinando términos para formar el siguiente o sustituyendo términos duplicados.
Las jugadas permitidas son:
- 1.- Cambiar dos números de Fibonacci consecutivos por su suma.
- 2a.- Cambiar dos unos por un dos.
- 2b.- Cambiar dos doses por un uno y un tres.
- 2c.- Cambiar dos números de Fibonacci iguales que no sean ni el uno ni el dos por el número de Fibonacci anterior del anterior y el siguiente.
 |
| Árbol de los primeros movimientos del "Zeckendorf game". Fuente |
Todas las transformaciones permitidas mantienen constante la suma de los números de la lista. Gana el último jugador que realiza un cambio. El juego termina siempre en la “representación de Zeckendorf” del número de unos inicial. La duración del juego y el ganador pueden variar dependiendo de los cambios efectuados.
Los autores demuestran en este artículo inicial que el segundo jugador tiene una estrategia ganadora si se comienza con más de dos unos pero, al tratarse de una prueba “no constructiva”, la demostración no describe la forma en la que se debe jugar para ganar.
En octubre de 2021, Wiliam Lee y Robert Bitler presentaron un algoritmo iterativo para encontrar una estrategia ganadora para el segundo jugador mucho más eficientemente que mediante una búsqueda exhaustiva “por fuerza bruta”. Para ello formularon el juego en forma de grafo dirigido sin ciclos y con un único nodo terminal.
Recientes resultados de un equipo dirigido por Steven J. Miller han demostrado que la complejidad computacional del juego Zeckendorf es tan alta que determinar una estrategia ganadora de forma explícita que valga para todos los posibles juegos particulares es un problema de los que en computación se denominan “intratables”, lo que a efectos prácticos quiere decir irresolubles con la tecnología actual.
El teorema de Zeckendorf en las TICs
Codificación de datos
El teorema de Zeckendorf ha encontrado también un ámbito de utilización en las tecnologías de la información y las comunicaciones. Particularmente en teoría de la codificación de datos y sus aplicaciones: compresión de datos, control y detección de errores, almacenamiento y transmisión de la información, criptografía y esteganografía.
El matemático israelí Aviezri Fraenkel nacido en 1929, especializado en teoría de juegos combinatorios, Medalla Euler 2005 e integrante del equipo que construyó el primer ordenador de Israel en el bienio 1954-1955, y Alberto Apostolico (1948-2015), profesor e investigador en ciencia e ingeniería computacional, propusieron en 1987 un nuevo sistema de codificación de datos cuyos “principales atributos son la robustez, que se manifiesta por la contención local de errores, y la codificación y decodificación simples” y del cual “la principal aplicación explorada es la transmisión de cadenas binarias en las que la longitud está en un rango desconocido”.
La clave de la propuesta radica en las propiedades de la representación de Zeckendorf de los números enteros. La no utilización de términos consecutivos de la sucesión de Fibonacci y la unicidad se traducen en la posibilidad de utilizar un “1” como separador de símbolos codificados consecutivos y en la consecución de un sistema de codificación unívocamente descifrable (cualquier secuencia codificada solo puede proceder de un único mensaje) de codificación y decodificación muy sencillas. Como un símbolo codificado no puede contener dos unos consecutivos, los errores en un bit de un símbolo pueden afectar a uno o dos códigos y no se propagan al resto.
Fraenkel junto con su discípulo Shmuel T. Klein posteriormente generalizaron y mejoraron el anterior sistema de codificación.
Seguridad de redes inalámbricas
Otro ejemplo de utilización del teorema de Zeckendorf en las TICs está relacionado con la seguridad de redes inalámbricas malladas (WMN). En ellas se utiliza el rastreo del origen de las ofensivas como la mejor solución para prevenir los ataques de denegación de servicio (DoS).
|
|
| Mouna Gassara |
Los tunecinos Mouna Gassara, siendo estudiante de Máster en la Escuela Nacional de Ingeniería de la Universidad de Sfax, y Faouzi Zarai, profesor en el Instituto Superior de Electrónica y Comunicaciones de la misma universidad, propusieron en 2016 una solución de rastreo de la IP de origen basada en el teorema de Zeckendorf para crear un nuevo protocolo de comunicación en redes de malla inalámbrica bautizado como SZNP (Secret Zeckendorf Number Protocol - Protocolo de número secreto de Zeckendorf) que permite construir con precisión la ruta de ataque sin introducir ningún gasto de ancho de banda y con un espacio de almacenamiento insignificante.
El teorema de Zeckendorf “generador” de poemas
El teorema de Zeckendor ha sido utilizado por el francés Paul Braffort en la creación de poemas, otra forma más artística que tecnológica de codificar información.
Paul Braffort ingresó en 1961 en OULIPO “Ouvroir de littérature potentielle”, a los pocos meses de su creación, desarrollando desde entonces una intensa actividad en el grupo. Desde sus orígenes, el “Taller de literatura potencial”, en ocasiones identificado de forma superficial con el ejercicio de complicadas acrobacias retóricas a modo de prescindible divertimento, está formado principalmente por escritores y matemáticos que trabajan explorando nuevas formas de creación literaria surgidas de la aplicación de restricciones (“contraites”) procedentes de las matemáticas.
Desde muy pronto y especialmente en el campo de los procedimientos combinatorios los informáticos propusieron aplicaciones para mejorar las investigaciones oulipianas. El peligro de confusión entre las actividades de Oulipo y ciertos experimentos informáticos que no estaban directamente relacionados con el proyecto llevó a Paul Braffort y Jacques Roubaud a proponer la creación de un nuevo grupo dedicado exclusivamente al binomio literatura-informática, fundando en 1981 el “Taller de literatura asistida por las matemáticas y los ordenadores”, ALAMO (Atelier de Littérature Assistée par la Mathématique et les Ordinateurs) en el que se integrarían además de oulipianos otros escritores, docentes e investigadores interesados en la lingüística, la inteligencia artificial o la pedagogía.
Hypertropes
Braffort desarrolló una novedosa forma poética que denominó “hipertropo” (hypertrope), en clara referencia al concepto de “hipertexto” utilizado en informática, inspirándose en una de las metarestricciones de la creación literaria sugeridas por Jacques Roubaud -solo utilizaremos una estructura matemática como la principal restricción de una obra literaria si también explotamos uno o más teoremas ligados a esta estructura-.
En 1979 Paul Braffort publicó, como nº 9 de la “Bibliothèque Oulipienne”, “Mes Hypertropes. Vingt-et-un moins un poèmes à programme”. La organización de este poemario se basa en la estructura matemática de la sucesión de Fibonacci explotando el teorema de Zeckendorf para crear el diagrama de flujo de las relaciones a nivel de significado establecidas entre los veinte poemas.
Según el propio Braffort declara en la introducción “0 Hors d'oeuvre”, donde, dicho sea de paso, cumple con la segunda restricción de Roubaud -un texto que obedezca a una restricción debe incluir una definición de dicha restricción-, “la transferencia de la estructura matemática sobre la restricción literaria es de orden semántico: el contenido del poema de rango n depende del contenido de los poemas cuyo rango forma la representación Zeckendorf de n”.
La primera página del poemario después de la cubierta es un “Graphe des matières” que indica de forma muy visual las relaciones entre los distintos poemas reflejando la descomposición de Zeckendorf de los primeros veinte números.
Por supuesto, los poemas cumplen otra serie de restricciones tanto oulipianas como clásicas en poesía.
Si analizamos como ejemplo el poema 13, “L'explication des explications”, encontramos que depende de los poemas 5 y 8 porque 13, que forma parte de la sucesión de Fibonacci, se obtiene como suma de los dos términos anteriores 8 y 5. A su vez influye en los poemas 14, 15, 16, 17, 18, 19 y 20 porque 13 figura en la descomposición de Zeckendorf de estos números. Por lo que elementos semánticos de los poemas 5 y 8 reaparecen en el poema 13 y los poemas del 14 al 20 dependen del contenido del poema 13.
Música con Zeckendorf
Mongoven es un compositor y doctor en en Filosofía en Artes y Tecnología de los Medios, nacido en California en 1979. Su interés investigador se orienta hacia la “sonificación” de objetos matemáticos, con especial dedicación a la representación sonora de sucesiones numéricas obtenidas tomando como base la de Fibonacci.
En un artículo publicado en 2010 establece un sistema de afinación temperada basada en la razón áurea y la sucesión de Fibonacci y describe un método de composición que lo utiliza, ofreciendo tres ejemplos de obras musicales creadas a partir de secuencias numéricas relacionadas con la de Fibonacci.
Posteriormente, en otro artículo publicado en 2011 junto a Ron Knott, muestran el potencial ofrecido por el teorema y la descomposición de Zeckendorf como base de un esquema creativo para la composición de música polifónica, explorando la posibilidad de convertir en parámetros musicales tanto los números de Fibonacci que aparecen en las descomposiciones de Zeckendorf de los números naturales como las posiciones en la sucesión de esos componentes. Los autores se interesan especialmente en la correspondencia de las propiedades matemáticas de la sucesión de representaciones de Zeckendorf con características sonoras que pueden ser percibidas. El artículo incluye tres composiciones, “Zeckendorf Representations” nº
17,
18 y
19
que muestran el efecto de distintas musicalizaciones de este tipo.
Un problema de probabilidad
Para finalizar con una aplicación más del teorema de Zeckendorf, veamos una forma de resolver el problema de probabilidad planteado al final del anterior artículo:
Calcular la probabilidad de obtener al menos dos caras sucesivas al lanzar una moneda n veces.
Como en muchos problemas de este tipo, es más fácil calcular la probabilidad de que no ocurra lo que se propone; en este caso de que no obtener dos caras seguidas al lanzar una moneda n veces.
Si representamos el resultado del lanzamiento de una moneda como “1” si sale cara y “0” si sale cruz, cada lanzamiento de una moneda n veces quedará representado por una secuencia de n cifras que pueden ser “0” ó “1”. Y viceversa, cada número binario de n cifras es la representación de un resultado. El número total de posibles resultados es 2n.
En esa correspondencia, se identifican los resultados sin dos caras seguidas con los números binarios de n cifras sin dos “unos” consecutivos. Es decir, con las representaciones de Zeckendorf que utilizan n cifras. Los números que pueden ser representados así son: 0,1,2,3,4,…,F(n+2)-1, considerando que F(i) indica el número que ocupa la posición i en la sucesión de Fibonacci, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5,…, es decir F(n+2) números.
Por lo que la probabilidad de no obtener dos caras consecutivas al lanzar n veces una moneda es: F(n+2)/2n y la probabilidad de obtener al menos dos caras consecutivas al lanzar n veces una moneda es: 1 - F(n+2)/2n
El problema y esta forma de resolverlo proceden de: J.R. Brown Jr., Zeckendorf’s theorem and some applications, Fibonacci Quart. vol. 2 Nº 3 (1964) 162–168
Qué son las Matemáticas y para qué sirven
El teorema de Zeckendorf es un resultado que, en su humildad matemática, manejando conceptos y procedimientos de demostración elementales puede servir de modesto ejemplo que encierra buena parte de la esencia de las Matemáticas: conocimiento expresado en forma de enunciados abstractos cuya veracidad es necesario demostrar y aplicación de esos resultados en diferentes campos, donde elementos en principio muy diversos comparten una estructura común atrapada en la abstracción. Algunas de esas aplicaciones solucionan problemas ya existentes, otras producen algo nuevo.
Acaba aquí un recorrido que comenzó buscando juegos de magia matemática para interesar al alumnado en la útima sesión de clase antes de comenzar unas vacaciones de Navidad. Ha estado bien el paseo.
No hay comentarios:
Publicar un comentario