El juego de Wythoff

Juego de resta matemática para dos jugadores

El juego de Wythoff se juega con dos montones de fichas.

El juego de Wythoff es un juego de resta matemática para dos jugadores , que se juega con dos montones de fichas. Los jugadores se turnan para quitar fichas de una o ambas pilas; al retirar fichas de ambas pilas, el número de fichas retiradas de cada pila debe ser igual. El juego termina cuando un jugador retira la última ficha o fichas, ganando así.

Una descripción equivalente del juego es que se coloca una única reina de ajedrez en algún lugar de una gran cuadrícula de casillas, y cada jugador puede mover la reina 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 la reina a la esquina. Las dos coordenadas cartesianas de la reina corresponden al tamaño de dos montones en la formulación del juego que consiste en retirar fichas de los montones.

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

Estrategia óptima

Una visualización del juego de Nim de Wythoff. El cuadrado inferior izquierdo es la posición (1,1) y los cuadrados rojos son posiciones frías. Tenga en cuenta que el cuadrado 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 moverse perderá con el mejor juego, mientras que en una posición caliente, el jugador al que le toca moverse ganará con el mejor juego. jugar. La estrategia óptima desde una posición caliente es pasar a cualquier posición fría accesible.

La clasificación de posiciones en frías y calientes 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 cual se pueda alcanzar una posición fría con 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 y A090909 en OEIS ) (Ver también OEIS : A072061 )

Para el juego misère de este juego, (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 un juego normal. esta frio.

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 suelo , entonces ( n _k , m _k ) es la k ^-ésima posición fría. Estas dos secuencias de números están registradas en la Enciclopedia en línea de secuencias enteras como OEIS : A000201 y OEIS : 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.

Ver también

• nim
• El juego de Grundy.
• restar un cuadrado
• Matriz Wythoff

Referencias

1. El juego de Wythoff en Cut-the-knot, citando el libro de Martin Gardner Penrose Tiles to Trapdoor Ciphers
2. Wythoff, WA (1907), "Una modificación del juego de nim", Nieuw Archief voor Wiskunde , 7 (2): 199–202

enlaces externos

• Weisstein, Eric W. "El juego de Wythoff". MundoMatemático .
• Suciedad, James. «El juego de Wythoff (Vuelve a casa)» (vídeo) . YouTube . Brady Harán . Archivado desde el original el 15 de diciembre de 2021 . Consultado el 21 de agosto de 2017 .