El teorema de Zeckendorf o “Magia y Fibonacci”

De lo que hablamos hoy aquí ya se habló en Divulgamat y ZTFNews.org,
y también en Gaussianos.

Edouard Zeckendorf fue un médico, oficial del ejercito y matemático belga que, en 1972, publicó el siguiente teorema:

Todo número entero positivo puede representarse de forma única como suma de números de Fibonacci (esto es, elementos de la sucesión de Fibonacci) distintos, de tal forma que dicha representación no contiene dos números de Fibonacci consecutivos.

Esta representación se denomina representación de Zeckendorf del número entero positivo en cuestión.

La demostración de la existencia se realiza por inducción. Dicho muy esquemáticamente, se supone el resultado cierto para cualquier entero positivo menor que uno dado \(N\), se escoge el mayor número de Fibonacci \(F_j\) menor o igual que \(N\) y se aplica la inducción al número \(N-F_j\).

Así, para obtener la representación de Zeckendorf de \(1954\), escogemos el mayor número de la sucesión que sea menor o igual que \(1954\), ya saben, \(1597\). La diferencia es \(1954-1597=357\). Ahora el número de Fibonacci más cercano a \(357\) es \(233\). Restando \(357-233=124\). Escogemos \(89\) como el siguiente número de Fibonacci en la representación de Zeckendorf, \(124-89=35\). Como \(34\) está en la sucesión de Fibonacci, la representación es:

\(1954=1597+233+89+34+1\).

(Por supuesto, para la representación de Zeckendorf no contamos el $atex 0$ y sólo tomamos uno de los dos términos iguales a \(1\))

La unicidad se basa en el siguiente lema:

La suma de cualquier conjunto no vacío de números de Fibonacci, no consecutivos, cuyo mayor elemento sea \(F_j\), es estrictamente menor que el siguiente término \(F_{j+1}\).

Una aplicación curiosa de esta representación es el paso de millas a kilómetros y viceversa. Dado que la razón aúrea es

\(\displaystyle\varphi\approx 1’6181033\ldots =\lim_{n\to\infty}\frac{F_n}{F_{n+1}}\),

muy parecida a la razón entre millas y kilómetros: \(1’6093\), para pasar (aproximadamente) \(N\) millas a kilómetros se puede sustituir cada término en la representación de Zckendorf de \(N\) por su siguiente en la sucesión de Fibonacci. Es decir

\(1954=1597+233+89+34+1\) millas

son aproximadamente

\(3162=2584+377+144+55+2\) kilómetros.

Otra aplicación del teorema es el siguiente juego, que consiste en adivinar cualquier número que el auditorio haya pensado entre \(1\) y \(100\). Para ello, una vez que se han puesto de acuerdo, a tus espaldas, en escoger un número, tú les vas presentando una por una estas 10 tarjetas con números “aleatorios”jeu-de-10-cartes-magiquesy ellos tienen que decir si su número se encuentra en ellas o no. Astútamente estas tarjetas las hemos fabricado de tal forma que comienzan por un número de Fibonacci, que está seguido por todos aquellos, mayores que él, que lo contienen en su representación de Zeckendorf.

Por ejemplo, si el número que han pensado es \(32\) escogerán las siguientes tarjetas cartes-avec-32y nosotros sólo tendremos que sumar los primeros números de cada tarjeta, cartes-avec-32-solutionpues la representación de Zeckendorf de \(32\) es \(32=21+8+3\).

El juego admite una variante que lo hace más divertido, puesto que sabemos que el número a adivinar no puede estar en dos tarjetas consecutivas. Una vez que nos señalen que el número está en una tarjeta sabemos, gracias al teorema de Zeckendorf, que no estará en la siguiente. Esto nos permite escoger entre el auditorio a algunas personas con “derecho a no decir la verdad”, a las que podremos preguntar justo después de que algún sincero haya señalado una tarjeta en la que aparece el número. Esto dará la apariencia de que nos ponen el juego más difícil al no saber si toda la información es cierta o no.

He escrito esta entrada gracias a Antonio Aranda y Ramón Piedra.
Esta entrada fue publicada en Curiosidades, Matemáticos. Guarda el enlace permanente.