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 reina de ajedrez se coloca 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 a la reina a la esquina.
Martin Gardner en su " columna de Juegos Matemáticos " de marzo de 1977 en Scientific American afirma que el juego se jugó 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 optima
Cualquier posición en el juego se puede describir mediante un par de números enteros ( n , m ) con n ≤ m , que describen 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 al que le toca mover perderá con la mejor jugada, mientras que en una posición caliente, el jugador al que le toca moverse ganará con la mejor jugada. tocar. La estrategia óptima desde una posición caliente es moverse 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:
- (0,0) es una posición fría.
- Cualquier posición desde la que se pueda alcanzar una posición fría en un solo movimiento es una posición caliente.
- 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 misere 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 −2, m −2 ) en el juego normal está 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
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 se registran 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
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.
Más de dos pilas
Al igual que Nim , el juego de Wythoff también se puede jugar con más de dos pilas de contadores. Los jugadores se turnan para quitar las fichas de una o más pilas; al retirar fichas de más de una pila, el número de fichas retiradas de cada pila debe ser igual.
Esto es como la reina del ajedrez en el ajedrez tridimensional , cuando hay tres pilas. De manera más general, cuando hay n pilas, esto es como la reina del ajedrez en el ajedrez n- dimensional.
Por ejemplo, (1,1,3) y (1,2,3) son posiciones calientes, ya que en estas dos posiciones un jugador puede alcanzar (0,1,2), que es una posición fría. (1,1,4) y (1,3,3) son posiciones frías.
Ver también
Referencias
- ^ Juego de Wythoff en Cut-the-knot , citandoel libro Penrose Tiles to Trapdoor Ciphers de Martin Gardner
- ^ Wythoff, WA (1907), "Una modificación del juego de nim" , Nieuw Archief voor Wiskunde , 7 (2): 199-202
enlaces externos
- Weisstein, Eric W. "Juego de Wythoff" . MathWorld .
- Grime, James. "Juego de Wythoff (llegar a casa)" (video) . YouTube . Brady Haran . Consultado el 21 de agosto de 2017 .