Nim (juego)

Nim es un juego en el que dos jugadores se turnan para recoger elementos que se dividen en varias pilas. En un movimiento, se puede tomar cualquier número de elementos (mayor que cero) de una pila. El jugador que toma el último objeto gana. En la versión clásica del juego, el número de montones es tres.

Un caso especial en el que solo hay una pila, pero el número máximo de elementos que se pueden tomar por turno es limitado, se conoce como el juego de Bache . Nim es un juego finito de información completa . El clásico juego de Nîmes es fundamental para el teorema de Sprague-Grundy . Este teorema establece que el juego ordinario de la suma de juegos no sesgados es equivalente al juego ordinario de Nim. Al mismo tiempo, cada término de juego imparcial corresponde a una pila de Nim, cuyo número de objetos es igual al valor de la función Sprague-Grundy para la posición de juego de este juego.

Historial del juego

El juego chino fue mencionado por los europeos ya en el siglo XVI. El nombre "nim" le fue dado al juego por el matemático estadounidense Charles Bouton , quien en 1901 describió la estrategia ganadora del juego . Hay varias opciones para el origen del nombre del juego:

del verbo alemán nehmen o del verbo inglés antiguo Nim , que significa "tomar";
Anónimo del verbo inglés Win ("ganar").

El juguete "Dr. Nim", una pequeña computadora de bola inventada en la década de 1960, no jugó en él, sino en el juego de Basche .

Juego de estrategia

En el caso general, se considera un grupo de elementos con elementos. Los jugadores se turnan. El movimiento es que el jugador toma de una pila de artículos. A cada posición del juego se le asigna una suma mínima de esta posición: el resultado de sumar los tamaños de todos los montones en el sistema numérico binario sin tener en cuenta la transferencia de bits, es decir, sumar los dígitos binarios de los números en el campo. de residuos módulo 2 : $pags$ ${\displaystyle N_{1},N_{2},\cdots N_{p))$ ${\ estilo de visualización i \ en [1, p]}$ ${\ estilo de visualización n \ en [1, N_ {i}]}$ ${\displaystyle S=N_{1}\oplus N_{2}\oplus \cdots \oplus N_{p))$

Una estrategia ganadora es dejar una posición con él-cantidad igual a cero después de su movimiento. Se basa en el hecho de que desde cualquier posición con una suma mínima que no es igual a cero, uno puede obtener una posición con una suma mínima cero en un movimiento, y desde una posición con una suma mínima cero, cualquier movimiento conduce a una posición con una suma nim distinta de cero.

Ejemplo : supongamos que hay tres pilas en el juego, contienen 2 (0010 en representación binaria), 8 (1000) y 13 (1101) elementos, respectivamente. La suma nim de esta posición es 7 (0111). Por lo tanto, la estrategia ganadora es tomar tres artículos de la tercera pila: quedarán 10 (1010) artículos y la suma mínima de la posición será 0 (0000). Suponga que, después de su turno, el oponente toma todos los elementos del primer montón; una estrategia ganadora sería tomar dos elementos del tercer montón. En este caso, después de su movimiento, las pilas contendrán 0 (0000), 8 (1000) y 8 (1000) elementos, respectivamente, la suma mínima seguirá siendo 0.

Opciones

Invertirlo

Los jugadores completan montones hasta un determinado . Disponible como misión en el juego de ordenador " Space Rangers ". El juego es equivalente a un nim con estado regular . $norte$ ${\displaystyle \{N-N_{i}\}_{i=1}^{p))$

Nim-Bashe

No puedes tomar más artículos. El juego es equivalente a un nim con estado normal. $k$ ${\displaystyle \{N_{i}\operatorname {mod} (k+1)\}_{i=1}^{p))$

Chocolate

Hay una barra de chocolate , una rebanada "envenenada". El jugador, por su cuenta, rompe el chocolate a lo largo de la línea y se come la parte no envenenada. Pierde el que se queda con el trozo envenenado. El juego es equivalente a nim con cuatro montones. $m\veces n$

avaro

En esta variante, pierde el jugador que tomó el último objeto. La estrategia ganadora es la misma que la estrategia ganadora del juego normal hasta el momento en que, como consecuencia de la jugada del jugador, deben quedar sobre la mesa un determinado número de montones con un único objeto en cada uno de ellos. En el caso de un avaro, el jugador debe dejar un número impar de montones, mientras que la estrategia ganadora de un juego regular requiere dejar un número par de montones para que la suma de neem sea cero. Esto se puede formular de la siguiente manera: si hay exactamente una pila que contiene más de un artículo, entonces tome todos los artículos de él o todos menos uno, de modo que quede un número impar de pilas individuales; de lo contrario, manténgase en la estrategia ganadora del juego normal.

Multinimo

Eliakim Moore propuso un caso más general del juego de Nîmes . En el juego , los jugadores pueden tomar elementos de un máximo de montones. Es fácil ver que el juego habitual es él . Para resolverlo, es necesario anotar los tamaños de cada montón en el sistema de numeración binaria y sumar estos números en el sistema de numeración -ario sin separación de sílabas. Si el número es 0, entonces la posición actual es perdedora; de lo contrario, es ganadora y se mueve desde ella a una posición con valor cero. $Nim_{i}$ $i$ $Nim_{1}$ $(yo+1)$

Bifurcado-nim

Matvey Bernstein propuso otra versión del juego. En él, puede dividir arbitrariamente cualquier montón en dos montones arbitrarios en lugar de un movimiento. En todos los demás aspectos, el juego se juega de acuerdo con las reglas habituales.

En cine y televisión

Este juego sirve como metáfora de lo que sucede en la película " El año pasado en Marienbad " [1] .

Véase también

Notas

↑ Oliver Knill. Matemáticas en películas : El año pasado en Marienbad . Matemáticas en el cine . Departamento de Matemáticas Universidad de Harvard. Fecha de acceso: 22 de junio de 2009. Archivado desde el original el 21 de febrero de 2012.

Literatura

Ball W., Coxeter G. Recreaciones y ensayos matemáticos. - M. : Mir, 1986. - S. 47-51.
Fomin SV Sistemas de numeración . - 5ª ed. - M. : Nauka, 1987. - S. 48.
Gardner M. Tres en raya. —M.: Mir, 1988. ISBN 5-03-001234-6 .
Jean-Paul Delahaye . Stratégies magiques au pays de Nim // Pour la science: Journal. - París: Belin, 2009. - T. 377 , No. 3 . - S. 88-93 . Archivado desde el original el 10 de junio de 2013.