Sobre Fibonacci
He de comenzar reconociendo que Fibonacci es mi debilidad. Una vez dejado esto claro nos metemos en harina.
Resulta muy curioso, y entretenido, el juego conocido como el nim de Fibonacci, consistente en ir retirando cuentas de una pila que inicialmente contiene n fichas. Los jugadores actúan por turno. En la primera jugada no es lícito retirar la pila completa, aunque sí en las sucesivas, siempre que se respeten las siguientes reglas:
Descomponemos el número 20 en números de Fibonacci, comenzando por el mayor posible (el 13) sumando después el mayor posible (5) y después el siguiente (2). Así que 20=13+5+2 es la descomposición buscada. Todo número entero puede descomponerse de forma única como una suma de números de Fibonacci; tal descomposición no contendrá nunca números F consecutivos.
El último número, el 2, es el número de cuentas que ha de retirar el primer jugador para ganar. El segundo queda imposibilitado por las reglas a tomar más del doble de 2, por consiguiente no puede reducir la pila (que ahora tiene 18 cuentas) al número F más cercano (el 13).
Supongamos que retire 4; la pila tendrá ahora 14 cuentas, número que se expresa como 14=13+1 en números F, por lo que el primero retirará ahora 1 cuenta. Prosiguiendo con esta estrategia, ganará.
Resulta muy curioso, y entretenido, el juego conocido como el nim de Fibonacci, consistente en ir retirando cuentas de una pila que inicialmente contiene n fichas. Los jugadores actúan por turno. En la primera jugada no es lícito retirar la pila completa, aunque sí en las sucesivas, siempre que se respeten las siguientes reglas:
- En cada turno es obligatorio retirar al menos una ficha.
- Ningún jugador puede retirar más del doble del número de fichas que haya retirado su oponente en el turno anterior.
- Gana la partida quien retire la última ficha.
Descomponemos el número 20 en números de Fibonacci, comenzando por el mayor posible (el 13) sumando después el mayor posible (5) y después el siguiente (2). Así que 20=13+5+2 es la descomposición buscada. Todo número entero puede descomponerse de forma única como una suma de números de Fibonacci; tal descomposición no contendrá nunca números F consecutivos.
El último número, el 2, es el número de cuentas que ha de retirar el primer jugador para ganar. El segundo queda imposibilitado por las reglas a tomar más del doble de 2, por consiguiente no puede reducir la pila (que ahora tiene 18 cuentas) al número F más cercano (el 13).
Supongamos que retire 4; la pila tendrá ahora 14 cuentas, número que se expresa como 14=13+1 en números F, por lo que el primero retirará ahora 1 cuenta. Prosiguiendo con esta estrategia, ganará.
1 comentario:
Muy interesante, no conocía el juego.
Me ha intrigado el que todo número se pueda descomponer de forma única como la suma de números F, sin repetir ninguno, de modo que no haya consecutivos. Y buscando en google solo he encontrado:
"La demostración es casi obvia. Restemos del número N el Fibonacci inferior más próximo Fi. La diferencia será menor de Fi(pues cada Fi es menor del doble del anterior) y podrá restarse de ella otro Fibonacci, claro está que también inferior a Fi. Y así procederemos sucesivamente hasta llegar al menor término posible"Según esto.
Para generar la descomposición, no siempre se coge el número F mayor posible. Para descomponer n, sí se empieza con el F(1) menor que n más próximo, pero luego se calcula n-F(1) y el siguiente número será el F(2) menor que n-F(1) más próximo, y así en adelante.
Con números sería para el 27=21+..., luego el F mayor posible menor que 27-21=6 que sería 5, 27=21+5+...El siguiente el F mayor posible menor o igual que 27-21-5=1, que sería 1, 27=21+5+1.
Espero no haberme equivocado. Se ha hecho algo pesado porque no reconoce los símbolos de mayor y menor.
Saludos.
Publicar un comentario