Juego de Wythoff

El juego de Wythoff se juega con dos pilas de contadores

El juego de Wythoff es un juego de resta matemática para dos jugadores, que se juega con dos pilas de fichas. Los jugadores se turnan para quitar las fichas de una o ambas pilas; al retirar fichas de ambas pilas, el número de fichas que se retiran de cada pila debe ser igual. El juego termina cuando una persona quita el último contador o contadores, ganando así.

Una descripción equivalente del juego es que una sola dama de ajedrez se coloca en algún lugar de una gran cuadrícula de cuadrados, y cada jugador puede mover la dama hacia la esquina inferior izquierda de la cuadrícula: sur, oeste o suroeste, cualquier número de pasos. El ganador es el jugador que mueve a la dama a la esquina.

Martin Gardner en su "columna de Juegos Matemáticos" de marzo de 1977 en Scientific American afirma que el juego se jugaba en China bajo el nombre de 捡石子 jiǎn shízǐ ("recoger piedras").^[1]​ El matemático neerlandés W. A. Wythoff publicó un análisis matemático del juego en 1907.^[2]​

Estrategia óptima

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.

Fórmula para posiciones frías

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.

Véase también

• Nim

• Juego de Grundy
• Matriz Wythoff

Referencias

1. Wythoff's game at Cut-the-knot, citando el libro Penrose Tiles to Trapdoor Ciphers de Martin Gardner
2. Wythoff, W. A. (1907), «A modification of the game of nim», Nieuw Archief voor Wiskunde 7 (2): 199-202 .
3. «A066096 - OEIS». oeis.org. Consultado el 31 de enero de 2021. 
4. «A090909 - OEIS». oeis.org. Consultado el 31 de enero de 2021. 
5. «A072061 - OEIS». oeis.org. Consultado el 31 de enero de 2021. 

Enlaces externos

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