Juego de Wythoff

Una visualización del juego de Wythoff de Nim. El cuadrado inferior a la izquierda es la posición (1,1) y los cuadrados rojos son posiciones frías. Téngase en cuenta que el cuadro ganador no está incluido en la imagen.

Cualquier posición en el juego puede describirse mediante un par de números enteros (n , m) con n ≤ m, que describen el tamaño de ambas pilas en la posición o las coordenadas de la reina. La estrategia del juego gira en torno a posiciones frías y posiciones calientes: en una posición fría, el jugador al que le toca mover perderá con el mejor juego, mientras que en una posición caliente, el jugador al que le toca moverse ganará con el mejor jugar. La estrategia óptima desde una posición caliente es pasar a cualquier posición fría accesible.

La clasificación de posiciones en caliente y fría se puede realizar de forma recursiva con las siguientes tres reglas:

1. (0,0) es una posición fría.
2. Cualquier posición desde la que se pueda alcanzar una posición fría en un solo movimiento es una posición caliente.
3. Si cada movimiento conduce a una posición caliente, entonces una posición es fría.

Por ejemplo, todas las posiciones de la forma (0, m ) y ( m , m ) con m  > 0 son calientes, según la regla 2. Sin embargo, la posición (1,2) es fría, porque las únicas posiciones que se pueden alcanzar de él, (0,1), (0,2), (1,0) y (1,1), están todos calientes. Las posiciones frías ( n , m ) con los valores más pequeños de n y m son (0, 0), (1, 2), (3, 5), (4, 7), (6, 10) y (8, 13). (secuencia A066096[3] y A090909[4] en OEIS) (Ver también OEIS:  A072061)[5]

Para la versión misère de este juego (aquél en el cual gana quien de acuerdo con las reglas, pierde), (0, 1) y (2, 2) son posiciones frías, y una posición ( n , m ) con m ,  n  > 2 es fría si y solo si ( n , m ) en juego normal esta frío.

Wythoff descubrió que las posiciones frías siguen un patrón regular determinado por la proporción áurea. Específicamente, si k es cualquier número natural y

${\displaystyle n_{k}=\lfloor k\phi \rfloor =\lfloor m_{k}\phi \rfloor -m_{k}\,}$

${\displaystyle m_{k}=\lfloor k\phi ^{2}\rfloor =\lceil n_{k}\phi \rceil =n_{k}+k\,}$

donde φ es la proporción áurea y estamos usando la función piso, entonces (n_k, m_k) es la k- ^ésima posición fría. Estas dos secuencias de números se registran en la Enciclopedia en línea de secuencias de números enteros como OEIS A000201 y A001950, respectivamente.

Las dos secuencias n_k y m_k son las secuencias de Beatty asociadas con la ecuación

${\displaystyle {\frac {1}{\phi }}+{\frac {1}{\phi ^{2}}}=1\,.}$

Como ocurre en general con los pares de secuencias de Beatty, estas dos secuencias son complementarias: cada número entero positivo aparece exactamente una vez en cada secuencia.

• Nim

• Juego de Grundy
• Matriz Wythoff

• Weisstein, Eric W. «Wythoff's Game». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
• Juego de Wythoff en YouTube