nymanmatematico: Conversión de Kilómetros a Millas y viceversa

Fibonacci, la representación de Zeckendorf y la conversión entre kilómetros y millas

La sucesión de Fibonacci, llamada así por el matemático italiano Leonardo de Pisa, Fibonacci (que la presentó en su obra Liber Abaci), es posiblemente una de las sucesiones numéricas más conocidas por los matemáticos y los no matemáticos. Y no es para menos, dada la gran cantidad de propiedades interesantes que posee y la manía que tiene de aparecer en los lugares más insospechados, además de por su relación con $\phi$ , el número áureo. Pero es posible que un objeto matemático como éste nunca sea totalmente conocido, siempre esconda algo. Hoy vamos a hablar de una interesante propiedad de esta sucesión que es poco conocida y que está relacionada con representaciones de números enteros positivos.

Sabemos que todo entero positivo puede representarse de forma única como suma de potencias de 2. De hecho es en esta propiedad en la que se basa el sistema de numeración binario, en el que cada número entero positivo se representa de una única forma con una sucesión de ceros y unos, correspondiendo un 1 a cada potencia de 2 que aparece en la representación y un 0 a cada potencia de 2 que no aparece. Por ejemplo, el 46 se representa de forma única como suma de potencias de 2 de la forma

$46=32+8+4+2=2^5+2^3+2^2+2^1,$

por lo que 46 en binario es:

$46=101110_{(2}.$

¿Qué tiene que ver esto de las representaciones de números enteros con los números de Fibonacci? Para responder a esta pregunta primero tenemos que introducir en esta historia al médico y matemático belga Edouard Zeckendorf, que además fue miembro del ejército belga y prisionero de guerra de 1940 a 1945. Él fue quien demostró el siguiente resultado, conocido como teorema de Zeckendorf:

Teorema de Zeckendorf:

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.

Vamos, que podríamos representar cada número entero positivo de una forma parecida a como lo hacemos con las potencias de 2 pero con números de la sucesión de Fibonacci, que, por cierto, no está de más recordar

$F_n=\begin{cases} 1 & \mbox{si } n=0 \\ 1 & \mbox{si } n=1 \\ F_{n-1}+F_{n-2} & \mbox{si } n \geq 2 \end{cases},$

asignando un 1 a una posición si el número de Fibonacci correspondiente aparece en la representación (como $F_0=F_1=1$ , para evitar problemas nos quedamos uno de ellos nada más, $F_1$ , para las representaciones) y un 0 a una posición si el número de Fibonacci correspondiente no está en ella. En el ejemplo que aparece un poco más adelante se verá más claro todo eso.

Zeckendorf publicó su resultado en The Fibonacci Quarterly en 1972, aunque al parecer lo conocía desde 1939. Puede accederse gratuitamente a su artículo en A generalized fibonacci numeration (aquí podéis ver las correcciones de algunas erratas que contenía dicho artículo).

¿Cómo encontramos la representación de Zeckendorf de un número entero positivo $n$ ? Pues, a priori es muy sencillo:

Tomamos el número de Fibonacci más grande de entre los que son menores que $n$ y se lo restamos a $n$ . Si queda cero es que el propio $n$ era un número de Fibonacci, y si no es así repetimos el proceso las veces que sea necesario hasta que una de las restas dé cero.

Vamos a hacerlo también con el 46, del que hace un rato calculamos la expresión en binario:

Como 46 no está en la sucesión de Fibonacci, su representación de Zeckendorf no es él mismo. Tomamos el número de Fibonacci más grande que sea menor que 46, que es el34, que por tanto estará en la representación.
Restamos: 46-34=12. Como 12 no es un número de Fibonacci buscamos el mayor elemento de la sucesión que sea menor que él, que es el 8. Entonces este 8 también estará en la representación.
Restamos: 12-8=4. Como 4 no está en la sucesión, buscamos el mayor número de Fibonacci que sea menor que él, que es el 3, que por tanto también estará en la representación.
Restamos: 4-3=1, que sí es un número de Fibonacci, por lo que también hay que tomarlo.
La representación queda como sigue:

$46=34+8+3+1=10010101_{(F}$

Cuanto menos curioso.

Esta representación de Zeckendorf también puede servir para definir una operación poco conocida: la denominada multiplicación de Fibonacci. Se define de la siguiente forma:

Dados dos números enteros positivos $a, b$ cuyas representaciones de Zeckendorf son las siguientes:

$a=\displaystyle{\sum_{i=0}^k F_{c_i}} \quad b=\displaystyle{\sum_{j=0}^l F_{d_j}}$

con $c_i, d_j \geq 1$ , definimos la multiplicación de Fibonacci de $a$ y $b$ , que denotaremos $a \circ b$ , así:

$a \circ b= \displaystyle{\sum_{i=0}^k \sum_{j=0}^l F_{c_i+d_j}}$

Veamos un ejemplo. Vamos a hacer la multiplicación de Fibonacci de 7 y 14, esto es, $7 \circ 14$ . Para ello, calculamos las representaciones de Zeckendorf de cada uno de ellos:

$7=5+2=F_4+F_2$ y $14=13+1=F_6+F_1$

Entonces:

$\begin{matrix} 7 \circ 14=F_{1+2}+F_{1+4}+F_{6+2}+F_{6+4}= \\ =F_3+F_5+F_8+F_{10}= 3+8+34+89=134 \end{matrix}$

Es fácil comprobar que esta operación es conmutativa (reordenando las sumas). Lo que es sorprendente es que también sea asociativa, hecho que probó Donald Knuth (parece que este señor tiene que estar siempre relacionado con cosas raras, como la notación de Knuth).

Y también podemos extender la sucesión de Fibonacci a índices negativos, consiguiendo así una forma de representar todo número entero (sea positivo y negativo) de forma única. Echadle un ojo a los trabajos de Zeckendorf y a los enlaces y podréis encontrar más información.

Para terminar, vamos a ver una manera de pasar de kilómetros a millas, y viceversa, usando esta representación. La clave está en el hecho de que la sucesión de los cocientes de cada número de Fibonacci entre el justo anterior converge al número áureo $\phi=(1+\sqrt{5})/2 \approx 1,618$ y que una milla son aproximadamente $1,609$ kilómetros.

¿Cómo podemos usar esto para nuestro objetivo? Muy sencillo. Supongamos que queremos expresar 72 millas en kilómetros. Lo que tenemos que hacer es encontrar la representación de Zeckendorf de 72 y después sustituir cada número de Fibonacci que aparezca en ella por el inmediatamente superior. La representación de Zeckendorf de 72 es

$72=55+13+3+1$