El juego de Wythoff

Juego de resta matemática para dos jugadores

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

El juego de Wythoff es un juego matemático de resta para dos jugadores , que se juega con dos pilas de fichas. Los jugadores se turnan para retirar fichas de una o ambas pilas; al retirar fichas de ambas pilas, la cantidad 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 sola reina de ajedrez en algún lugar de una gran cuadrícula de cuadrados 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 hacia la esquina. Las dos coordenadas cartesianas de la reina corresponden a los tamaños de dos pilas en la formulación del juego que implica retirar fichas de las pilas.

Martin Gardner, en su columna de marzo de 1977 sobre los juegos matemáticos en la revista Scientific American, afirma que el juego se jugaba en China con el nombre de 捡石子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

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. Nótese que el cuadrado ganador no está incluido en la imagen.

Cualquier posición en el juego puede ser descrita por un par de números enteros ( n , m ) con n  ≤  m , describiendo el tamaño de ambos montones 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 a quien le toca mover perderá con la mejor jugada, mientras que en una posición caliente, el jugador a quien le toca mover ganará con la mejor jugada. La estrategia óptima desde una posición caliente es moverse a cualquier posición fría alcanzable.

La clasificación de posiciones en calientes y frías 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 la posición es fría.

Por ejemplo, todas las posiciones de la forma (0, m ) y ( m , m ) con m  > 0 son calientes, por la regla 2. Sin embargo, la posición (1,2) es fría, porque las únicas posiciones a las que se puede llegar desde ella, (0,1), (0,2), (1,0) y (1,1), son todas 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 miserable 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 sólo si ( n , m ) en el juego normal es fría.

Fórmula para posiciones frías

Wythoff descubrió que las posiciones frías siguen un patrón regular determinado por la proporción áurea . En concreto, 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 de piso , 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 de números enteros 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 entero positivo aparece exactamente una vez en cada secuencia.

Véase 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". MathWorld .
• Grime, James. "Wythoff's Game (Get Home)" (video) . YouTube . Brady Haran . Archivado desde el original el 2021-12-15 . Consultado el 21 de agosto de 2017 .