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.
Si n es un número de Fibonacci, el segundo jugador puede ganar siempre; en cambio si no es así el ganador, si sigue la estrategia correcta, será el primero. Si una partida comienza por ejemplo con 20 fichas (que no es un número de Fibonacci), ¿cuántas debe retirar el primer jugador para asegurarse la victoria?
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á.
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
Publicar un comentario