El sistema de Fibonacci

El juego de Fibonacci nim es un juego matemático de resta , una variante del juego de nim . Los jugadores se turnan para quitar monedas de una pila, en cada movimiento toman como máximo el doble de monedas que en el movimiento anterior y ganan al tomar la última moneda. Los números de Fibonacci ocupan un lugar destacado en su análisis; en particular, el primer jugador puede ganar si y solo si el número inicial de monedas no es un número de Fibonacci. Se sabe que una estrategia completa funciona mejor en juegos con una sola pila de fichas, pero no en variantes del juego con múltiples pilas.

El juego de Fibonacci se juega con dos jugadores que se turnan para retirar monedas u otras fichas de una pila. En el primer movimiento, no se permite que un jugador tome todas las monedas y, en cada movimiento posterior, la cantidad de monedas retiradas puede ser cualquier número que sea como máximo el doble del movimiento anterior. Según la convención de juego normal , el jugador que toma la última moneda gana. ^[1]

El juego fue descrito por primera vez por Michael J. Whinihan en 1963, y atribuyó su invención al matemático de la Universidad Estatal de Oregón Robert E. Gaskell. Se llama Fibonacci nim porque los números de Fibonacci ocupan un lugar destacado en su análisis. ^[2]

Este juego debe distinguirse de un juego diferente, también llamado Fibonacci nim, en el que los jugadores pueden eliminar cualquier número de Fibonacci de monedas en cada movimiento. ^[3]

La estrategia para jugar mejor en Fibonacci nim implica pensar en el número actual de monedas como una suma de números de Fibonacci . ^[2] Hay muchas formas de representar números como sumas de números de Fibonacci, pero solo una representación que usa cada número de Fibonacci como máximo una vez y evita pares consecutivos de números de Fibonacci; esta representación única se conoce como su representación Zeckendorf . Por ejemplo, la representación Zeckendorf de 10 es 8 + 2; aunque 10 también se puede representar como sumas de números de Fibonacci de otras formas, como 5 + 5 o 5 + 3 + 2, esas otras formas no cumplen la condición de usar solo una vez cada número de Fibonacci y evitar pares consecutivos de números de Fibonacci como los pares 2, 3 y 3, 5. La representación Zeckendorf de cualquier número se puede encontrar mediante un algoritmo voraz que resta repetidamente el mayor número de Fibonacci posible, hasta llegar a cero. ^[4]

La estrategia del juego también implica un número llamado "cuota", que puede denotarse como q . Este es el número máximo de monedas que se pueden retirar en ese momento. En el primer movimiento, se pueden retirar todas las monedas menos una, por lo que si el número de monedas es n , la cuota es q = n − 1. En los movimientos posteriores, la cuota es el doble del movimiento anterior. ^[2]

Según estas definiciones, el jugador que está a punto de mover puede ganar siempre que q sea mayor o igual que el número de Fibonacci más pequeño en la representación de Zeckendorf, y perderá (con el mejor juego del oponente) en caso contrario. En una posición ganadora, siempre es un movimiento ganador retirar todas las monedas (si esto está permitido) o, en caso contrario, retirar una cantidad de monedas igual al número de Fibonacci más pequeño en la representación de Zeckendorf. Cuando esto es posible, el jugador oponente necesariamente se enfrentará a una posición perdedora, porque la nueva cuota será menor que el número de Fibonacci más pequeño en la representación de Zeckendorf del número restante de monedas. ^[2] También pueden ser posibles otros movimientos ganadores. ^[5] Sin embargo, desde una posición perdedora, todos los movimientos conducirán a posiciones ganadoras. ^[2]

La representación Zeckendorf de un número de Fibonacci consiste en ese único número. Por lo tanto, cuando la pila inicial tiene un número de Fibonacci n de monedas, el número de Fibonacci más pequeño en la representación Zeckendorf es simplemente n , mayor que la cuota inicial n − 1 . Por lo tanto, un número de Fibonacci como pila inicial es perdedor para el primer jugador y ganador para el segundo jugador. Sin embargo, cualquier número inicial de monedas que no sea Fibonacci tiene números de Fibonacci más pequeños en su representación Zeckendorf. Estos números no son mayores que la cuota inicial, por lo que siempre que el número inicial de monedas no sea un número de Fibonacci, el primer jugador siempre puede ganar. ^[1]

Por ejemplo, supongamos que inicialmente hay 10 monedas. ^[6]

• La representación Zeckendorf del 10 es 10 = 8 + 2, y la cuota inicial es 9, mayor que el número de Fibonacci más pequeño, 2, en la representación Zeckendorf, por lo que el primer jugador puede ganar. Una jugada ganadora del primer jugador sería eliminar el número de Fibonacci más pequeño en esta representación, 2, dejando 8 monedas.
• Después de este movimiento, quedan 8 monedas, con la representación de Zeckendorf 8, y la nueva cuota es 4, lo que significa que el segundo jugador puede retirar como máximo 4 monedas, no lo suficiente para alcanzar el número más pequeño en la representación de Zeckendorf. Quitar 3 o 4 monedas permitiría al primer jugador ganar inmediatamente; supongamos en cambio que el segundo jugador toma 2 monedas.
• Esto deja 6 = 5 + 1 monedas, con una cuota de 4, mayor que la 1 en la representación de Zeckendorf. El primer jugador puede tomar nuevamente el número de Fibonacci más pequeño en esta representación, 1, lo que deja 5 monedas.
• Con una pila de 5 monedas, la representación de Zeckendorf es 5, pero la cuota es 2, un número menor. El segundo jugador podría tomar dos monedas, pero perdería inmediatamente, así que supongamos que el segundo jugador toma solo una moneda.
• Después de este movimiento, el número de monedas es 4 = 3 + 1, y la cuota es 2. El primer jugador toma nuevamente el número de Fibonacci más pequeño en la representación de Zeckendorf, 1, quedando 3 monedas.
• Ahora, independientemente de si el segundo jugador toma una o dos monedas, el primer jugador ganará el juego en el siguiente movimiento.

El juego de Fibonacci es un juego imparcial en el que los movimientos disponibles desde cualquier posición no dependen de la identidad del jugador que está a punto de mover. Por lo tanto, el teorema de Sprague-Grundy se puede utilizar para analizar una extensión del juego en la que hay múltiples pilas de monedas y cada movimiento elimina monedas de una sola pila (como máximo el doble de las que se eliminaron en el movimiento anterior de la misma pila). Para esta extensión, es necesario calcular el valor nim de cada pila; el valor del juego de múltiples pilas es la suma nim de estos valores nim. Sin embargo, no se conoce una descripción completa de estos valores. ^[7]

También se ha estudiado una variante diferente del juego, en la que se utilizan varias pilas, que limita el número de piedras en cada movimiento al doble del número del movimiento anterior, independientemente de si el movimiento anterior fue a la misma pila. ^[8]