Nim Wythoff

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 23 de octubre de 2017; las comprobaciones requieren 2 ediciones .

El nim de Wythoff , o el juego de Wythoff , es un juego matemático estratégico para dos jugadores con dos montones de fichas. Los jugadores toman turnos tomando fichas de una o ambas pilas; en este último caso, se toman fichas iguales de ambos montones. Gana el que se lleva la última o las últimas fichas.

Martin Gardner , en From Penrose Mosaics to Secure Ciphers (Capítulo 8), afirma que el juego se conoce en China como 捡石子jianshizi [1] [2] ("tomar piedras"). [3] El matemático holandés Willem Wiethoff publicó un análisis matemático del juego en 1907.

Estrategia óptima

Cualquier posición en el juego puede ser descrita por un par de números ( n , m ), con n ≤, donde n y m  son el número de fichas en montones. La estrategia del juego se basa en la definición de buenas y malas posiciones : mala posición (ing.: posición fría ) - una posición perdedora incluso con acciones óptimas del jugador que está en ella; una buena posición ( caliente ) es aquella desde la cual el jugador gana con acciones óptimas. La estrategia óptima para un jugador en una buena posición es mover el juego a cualquiera de las malas posiciones, dando derecho a mover al oponente, quien, a su vez, moverá el juego a una buena posición para el primer jugador.

La clasificación de posiciones en buenas y malas se puede hacer recursivamente usando las siguientes tres reglas:

  1. (0,0) - mala posición (pérdida).
  2. Cualquier posición desde la que se pueda alcanzar una mala posición en un solo movimiento es una buena posición.
  3. Una posición desde la cual cada movimiento conduce a una buena posición es una mala posición.

Por ejemplo, todas las posiciones de la forma (0, m ) y ( m , m ) para m > 0 son buenas (según la regla 2). A su vez la posición (1,2) es mala, porque desde ella solo se puede llegar a las posiciones (0,1), (0,2) y (1,1), y todas son buenas, como se indica en la frase anterior. Las primeras posiciones malas ( 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).

Fórmula para malas posiciones

Wythoff demostró que las malas posiciones siguen un patrón definido por la proporción áurea . En particular, si k  es un número natural arbitrario, y

,

donde φ es la proporción áurea, entonces ( n k , m k ) es la k -ésima mala posición. Estas dos secuencias se denominan secuencias de Wythoff inferior y superior y están numeradas A000201 y A001950 respectivamente en la Enciclopedia de secuencias enteras.OEISicon luz.svg OEISicon luz.svg

Las dos secuencias n k y m k son las secuencias de Beatty asociadas con la ecuación

Las dos secuencias son complementarias : cada entero positivo aparece exactamente una vez en cualquier secuencia.

Véase también

Referencias

  1. ↑ Nikolai Nikolaevich Vorobyov. números de Fibonacci. M.: Nauka, 1978
  2. ↑ Matulis A., Savukinas A., Queen - into the corner, "jianshizi" y números de Fibonacci, Kvant, 1984
  3. ↑ Wythoff's game at Cut-the-knot Archivado el 9 de febrero de 2021 en Wayback Machine , citando el libro Penrose Tiles to Trapdoor Ciphers de Martin Gardner .

Enlaces