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}.

Edouard Zeckendorf¿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 el 34, 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

Según lo anterior, esto nos dice que 72 millas serán, aproximadamente

89+21+5+2=117 kilómetros.

Si queremos pasar de kilómetros a millas hacemos lo mismo, pero en este caso sustituimos cada número de Fibonacci por el anterior.


Fuentes y enlaces relacionados:

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

13 Comentarios

  1. Un pequeño detalle tonto. Donde pone “La representación de Zeckendorf de 72 es 55 + 13 + 3 + 1” ¿Ese 1 es el primero o el segundo uno de la sucesión de Fibonacci? Porque si luego tenemos que sustituirlo por el término inmediatamente superior no es lo mismo volver a poner otro 1 que pasarlo a un 2.

    Publica una respuesta
  2. GOB, fíjate que justo después de recordar la definición de la sucesión de Fibonacci comento que para las representaciones se excluye el primer 1, por lo que ése siempre será el “segundo” 1.

    Publica una respuesta
  3. Dices en la definición de la representación de Zeckendorf que “no contiene dos números de Fibonacci consecutivos”, por tanto 14 debería ser: F_6+F_1

    Publica una respuesta
  4. ¡¡Ouch!! Cierto Davidmh. La cosa es que hice pruebas con varios números y al final se me pasó escribirlo todo bien. Lo arreglo ahora mismo. Muchas gracias por el aviso 🙂

    Publica una respuesta
  5. Aunque odio las matematicas esto me pareció interesante sobre la representación de Zeckendorf 🙂

    Publica una respuesta
  6. Que cómodo, a partir de ahora me llevare una representación de Zeckendorf para pasar de Millas a Kms.

    Publica una respuesta
  7. Vaya, no me había fijado en esa línea sobre $F_1 = 1$. Aclarado entonces 😉

    Justo hace poco estuve leyendo sobre los sistemas de numeración en bases que no sean naturales, como el número áureo, cualquier racional, raíces n-ésimas, pi, e, i… Recomendaría a todos echar un ojo a estos temas que son interesantes.

    Publica una respuesta
  8. Llevo mucho tiempo siguiendo tus post, y nunca te había hecho ningún comentario. Fascinante artículo. Nunca deja de sorprenderme lo que tiene oculto la sucesión de Fibonacci. Un saludo y enhorabuena por tu página

    Publica una respuesta
  9. Aclarar que se está refiriendo a millas anglosajonas (statute miles). Para la navegación aerea y marítima se usa la milla nautica (1852 m) que es aproximadamente la longitud de un arco de 1′ (un minuto) de meridiano terrestre.

    Publica una respuesta
  10. Una pregunta, esta propiedad parece que podría cumplirse para cualquier serie de números siempre y cuando cumpla ciertas propiedades, alguna idea de cual sería el resultado general?

    Saludos

    Publica una respuesta
  11. Estaba pensando lo mismo que Javier… Imaginemos una sucesión de números naturales, estrictamente creciente y tal que el 1 es su primer término y, además, que cada término sea menor que el doble del anterior. ¿Podemos usar el mismo razonamiento que en el post para concluir que cualquier natural puede ser expresado como suma de términos distintos de esa sucesión?

    Sea $N$ un natural (que no esté en la sucesión). Restamos el mayor de los términos de la sucesión que esté por debajo de él, $a_{p_{1}}$. Como el término $a_{p_{1}+1}$ es menor que $2 a_{p_{1}}$, y $N<a_{p_{1}+1}$, tenemos que $N_{2}=N-a_{p_{1}}<a_{p_{1}}$. Aplicamos el mismo procedimiento a $N_{2}$ para obtener un nuevo elemento $a_{p_{2}}$ y proseguimos hasta que la diferencia sea nula (lo cual está garantizado ya que la sucesión $N_{i}$ es decreciente.

    Probemos con un ejemplo: Sea la sucesión: {1, 2, 3, 4, 7, 11, 20, 35, 60, 100,…} donde lo único que he forzado es que cada término sea menor que el anterior.

    10 = 7 + 3
    74 = 60 + 11 + 2 + 1
    176 = 100 + 60 + 11 + 4 + 1

    Sea ahora la sucesión {1, 2, 4, 6, 9, 17, 20, 33, 59, 108, 109, …} (lo único que hay que tener en cuenta es que cada término sea menor o igual que el doble del anterior).

    10 = 9 +1
    52 = 33 + 17 + 2
    103 = 59 + 33 + 9 + 2

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: La sucesión de Fibonacci, llamada así por el matemático italiano Leonardo de Pisa, Fibonacci…
  2. Fibonacci, la representación de Zeckendorf y la conversión entre kilómetros y millas - [...] "CRITEO-300x250", 300, 250); 1 meneos Fibonacci, la representación…
  3. Fibonacci, la representación de Zeckendorf y la conversión entre kilómetros y millas - [...] Fibonacci, la representación de Zeckendorf y la conversión entre kilómetros y millas gaussianos.com/fibonacci-la-representacion-de-zeckendorf-...  por gabrielin…
  4. Fibonacci, la representación de Zeckendorf y la conversión entre kilómetros y millas – Gaussianos | | goenkale - [...] Fibonacci, la representación de Zeckendorf y la conversión entre kilómetros y millas – Gaussianos | Fibonacci, la representación de…
  5. Un jersey muy matemático - Gaussianos | Gaussianos - [...] muy matemático. Un jersey en el que aparece el triángulo de Pascal, los primeros términos de la sucesión…
  6. Yo también quiero hacer magia… ¿o son matemáticas? « :: ZTFNews.org - [...] explicación del truco se basa en el teorema de Zeckendorf que dice [...]
  7. El teorema de Zeckendorf o “Magia y Fibonacci” | Blog del Departamento de Álgebra - […] De lo que hablamos hoy aquí ya se habló en Divulgamat y ZTFNews.org, y también en Gaussianos. […]

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

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