Cinco problemas equivalentes al de Fibonacci

Voy a plantear en este post cinco problemas de combinatoria que son equivalentes al problema de los conejos de Fibonacci, en el sentido de que dan lugar a la misma sucesión (y a la misma recurrencia). La solución de cada uno de ellos se detiene en el modelo, es decir, en el razonamiento por recurrencia que conduce a plantearlo. 

1. Subconjuntos sin consecutivos

¿De cuántas formas se puede elegir un subconjunto de {1,2,…,n} de manera que no contenga números consecutivos?

Solución
Sea un el número de subconjuntos de {1,2,….n} sin números consecutivos. Cada subconjunto aceptable según la restricción, ya sea que contiene el 1 o bien no lo contiene.

Si contiene el 1 entonces no puede contener el 2 y se ve que el número de subconjuntos que contienen el 1 es un−2 --pues es el número de subconjuntos de {3,4,…,n}.

Por otro lado, si el subconjunto no contiene el 1, entonces el número de subconjuntos de esta clase son un−1 --dado que es el número de subconjuntos de {2,3,…,n}.

En resumen, un=un−1+un−2. (Claramente, u1=1,u2=2 --se deja como ejercicio su justificación.)

2. n-Cadenas binarias con dos ceros consecutivos

¿De cuántas formas se puede construir una n-cadena de ceros y unos con dos ceros consecutivos?

Solución
Sea un el número de cadenas binarias de longitud n con dos ceros
consecutivos. Claramente, una cadena de longitud 1 no puede tener dos ceros consecutivos, y solamente hay una de longitud dos con dos ceros consecutivos. Es decir, u1=0,u2=1.

Consideremos ahora el caso general. Cada cadena de longitud n con dos ceros consecutivos es de una de tres clases: empieza con 00 o con 01 o con 1.

Si empieza con 00, el resto de la cadena es una cadena de longitud n−2 sin restricción.

Por otro lado, si empieza con 01, el resto de la cadena es una cadena de longitud n−2 con dos ceros consecutivos.

Finalmente, si empieza con 1, el resto de la cadena es una cadena de longitud n−1 con dos ceros consecutivos.

En resumen, el modelo recursivo para este problema es:

un=2n−2+un−2+un−1

con u1=0,u2=1

3. Sus dígitos son 1 y/o 2 y suman n

¿Cuántos números con 1 y 2 como dígitos son tales que éstos suman n? Ejemplo: 111, 12, 21 son los tres números que cumplen para n=3.

Solución
Sea un el número de números que cumplen para n. Claramente, u1=1,u2=2. En el caso de n mayor que 2, se puede razonar recursivamente como sigue:
Los números que cumplen se pueden clasificar en dos clases excluyentes y exhaustivas. Los que empiezan con 1 y los que empiezan con 2.
Si empiezan con 1, son un−1 --pues el problema se reduce a contar los números con 1 y 2 como dígitos y tales que éstos suman n−1.
Si empiezan con 2, son Un−2 --siguiendo un razonamiento similar. Por tanto un=un−1+un−2.
Otra forma: Considerando el último dígito, éste puede ser 1 o bien 2. Los números que terminan en 2 son un−2 y los que terminan en 1 son un−2

4. n-Cadenas binarias sin unos consecutivos

¿De cuantas formas se puede formar una cadena de ceros y unos de longitud n sin unos consecutivos?

Solución
Los números ya sea que inician con cero o bien con uno. Los que empiezan con cero son un−1 y los que empiezan con uno son un−2 --porque en realidad deben empezar con 10. Por tanto, un=un−1+un−2.

5. Tiempo de espera hasta dos águilas consecutivas

En una secuencia de n volados ¿cuántos resultados no tienen dos águilas consecutivas, excepto al final?

Solución
Sea un el número buscado. Los resultados, ya sea inician con águila (A) o bien con sello (S). Si inician con águila son un−2; si con sello, son un−1. Por tanto, un=un−1+un−2

Tomado de:

Mate Mat

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 , 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

por lo que 46 en binario es:

 
¿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

asignando un 1 a una posición si el número de Fibonacci correspondiente aparece en la representación (como , para evitar problemas nos quedamos uno de ellos nada más, , 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 ? Pues, a priori es muy sencillo:

Tomamos el número de Fibonacci más grande de entre los que son menores que y se lo restamos a . Si queda cero es que el propio 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:
• 
  
  

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 cuyas representaciones de Zeckendorf son las siguientes:

con , definimos la multiplicación de Fibonacci de y , que denotaremos , así:

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

y

Entonces:

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 y que una milla son aproximadamente 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

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

   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.

Tomado de:

Gaussianos 

Ahora puedes trabajar sobre una espiral logaritmica

Desde hace décadas al nautilo se la considerado una figura especial dentro del mundo matemático, ya que su forma ha sido sinónima con las espirales logaritmicas, especialmente con la espiral Fibonacci, asociada con la razón y el rectángulo áureos. Especialmente cuando ha sido razón para hacerlo portada de textos escolares desde nivel elemental a secundario.

Nautilus II Table by Marc Fish

Marc Fish logró crear esta mesa (y otras 4) de nautilo a comisión, mencionando que ésta en particular tendrá un hogar cerca del Canal Inglés.

Fuente:

La Covacha Matemática

Conocer Ciencia TV

Conozca más sobre Fibonaccii (y los números grandes, muy grandes) en la siguiuente presentación que incluimos en uno de nuestros programas de televisión:

Fibonacci y los números grandes from Conocer Ciencia

Conocer Ciencia: ciencia sencilla, ciencia divertida, ciencia fascinante...

Premio Nobel de Química para el 'padre' de los cuasicristales

Modelo atómico de los cuasicristales. | AFP

Hace casi nueve siglos que Leonardo de Pisa, un matemático italiano del medievo también conocido como Fibonacci, describió la famosa secuencia del mismo nombre y que consiste en una sucesión que se inicia con 0 y 1 y que continúa con la suma de los dos últimos números de la secuencia (es decir, 0,1,1,2,3,5,8...). A simple vista poco o nada parece tener que ver este tipo de secuencias con la construcción de cristales. Pero los cristales son el producto de la traslación espacial repetitiva de una celda concreta, particular para cada tipo de cristalización y que configura una estructura simétrica.

La relación sigue sin aparecer por ningún lado. El nexo está precisamente en los cuasicristales, cuyo descubrimiento ha motivado a la Real Academia Sueca de Ciencias para conceder el Premio Nobel de Química 2011 a Daniel Shechtman, del Instituto Israelí de Tecnología de Haifa.

Los cuasicristales son estructuras atómicas construidas mediante mosaicos similares a los del mundo árabe y que adornan los muros de palacios como el de la Alhambra de Granada, pero que nunca se repiten a sí mismas. Es decir, no siguen el patrón de construcción de los cristales convencionales que forman estructuras simétricas.

Crecimiento cuasiperiódico

Pero, ¿cómo crecen estos cristales? La respuesta la tiene nuevamente el matemático medieval. La secuencia cuasiperiódica de Fibonacci se obtiene mediante unas reglas de sustitución bien sencillas. Si cogemos dos segmentos, uno largo (L) y otro corto (C), y los ordenamos según estas sencillas reglas: L pasa a ser LC y C se transforma en L, el resultado será una secuencia infinita LCLLCLCLLC... en la que no existe ninguna pauta periódica, pero sí cuasiperiódica. "El número de eles dividido por el número de ces tiende a un número irracional muy popular entre los artistas del Renacimiento, el 'número de oro', que está directamente relacionado con la geometría del pentágono regular", explicaba el físico Manuel Torres en un artículo publicado en El Cultural.

Según cita la academia sueca en un comunicado, la configuración encontrada en los cuasicristales ha sido considerada como imposible, sin embargo, Daniel Shechtman, nacido en Tel Aviv en 1941, ha librado una fiera batalla contra la ciencia establecida. Su trabajo ha cambiado la forma en la que los químicos conciben la materia sólida.

Hasta el desembarco de Shechtman, los científicos creían que en todos los sólidos los átomos se ordenaban para formar cristales siguiendo patrones simétricos que se repiten periódicamente una y otra vez. Sin embargo, el químico israelí observó, usando un microscopio electrónico durante uno de sus experimentos, una estructura que se alejaba de esta configuración y el patrón que la configuraba no se repetía. Sus colegas alegaban que esto era tan imposible como fabricar un balón de fútbol sólo con hexágonos (polígonos con seis esquinas), cuando todo científico sabe que para hacer una esfera es necesario alternar polígonos de seis y de cinco vértices.

Mal conductor y muy resitente

Los descubrimientos de Shechtman han permitido producir cristales de muy diferentes tipos y han sido encontrados, por una empresa Sueca, en una forma del acero, donde estas estructuras refuerzan el material como si de una armadura se tratase.

Los cuasicristales son malos conductores de la electricidad y extremadamente duros y resistentes a la deformación, por lo que se emplean para recubrimientos protectores antiadherentes. En la actualidad, otros equipos están desarrollando las futuras aplicaciones de estos cuasicristales, que van desde la fabricación de sartenes hasta la construcción de motores diésel.

Fuente:

El Mundo Ciencia

Conozca más sobre Leonardo Fibonacci en la siguiente presentación de Conocer Ciencia TV:

Fibonacci y los números

More PowerPoint presentations from Conocer Ciencia