9:54 PM
NIM Y MATEMÁTICA

NIM Y MATEMÁTICA

ESTRATEGIA GANADORA:

En 1910 Charles Leonard Bouton, profesor de matemáticas de la Universidad de Harvard, bautizó el juego con el nombre de Nim, un verbo inglés en desuso que significa retirar, quitar o robar, y publicó un análisis completo del juego (Charles L. Bouton, «Nim, a Game with a Complete Mathematical Theory», publicado en 1910 en Annals of Mathematics, serie II, vol 11, págs. 93-94).

En cuanto a la estrategia del Nim, el análisis de Bouton clasifica las posiciones en dos clases: las ‘seguras’ y las ‘inseguras’. Una posición es segura si la suma sin arrastre de los números de las fichas de cada fila, expresados en el sistema binario, resulta en una ristra de ceros (cuando la suma de cada columna se convierte a 0 si es par y a 1 si es impar); en caso contrario, la posición se califica de insegura. Ahora es fácil demostrar que una posición segura se convierte necesariamente en insegura en un turno (ver T1 más abajo), mientras que de una posición insegura se puede pasar siempre a una segura si se juega adecuadamente (ver T2) (en otro caso, lo más probable es que se obtenga nuevamente otra posición insegura). Según esto, la estrategia ganadora consiste en dejar una posición segura en cuanto sea posible, y seguir manteniendo en adelante ese tipo de configuración. En la versión ‘el que retira la última gana’, cuando quedan dos filas se va dejando la configuración de ambas filas con el mismo número de fichas, que es segura, y que gana necesariamente (al final el contrario deberá dejar dos filas de una ficha, o una fila solitaria, posición con la que perderá en ambos casos). Si se juega según la modalidad ‘el que retira la última pierde’, la estrategia es la misma, salvo llegado el momento en que hay que cambiar de proceder, cosa que ocurre cuando queda solamente una fila con más de una ficha, posición que se alcanza necesariamente, siendo insegura. En ese caso se deben retirar todas las fichas de esa fila o bien todas menos una, para dejar la posición con un número impar de filas de una ficha, lo que garantiza de nuevo la victoria.

Al tratarse de sumas binarias sin arrastre, con un poco de entrenamiento se pueden hacer los cálculos ayudándose de los dedos de una mano, extendiéndolos (1) o encogiéndolos (0). Así es posible manejar filas con hasta 31 fichas. La mano se esconde tras la espalda o en un bolsillo para que no se advierta el conteo.

Extraído del sitio de Pedro Crespo:
http://pedroweb.dyndns.org/matematicas/nimhistoria.htm

Demostración de una estrategia ganadora para el juego del Nim

Teorema- El primer jugador (el que abre el juego) tiene una estrategia ganadora si y sólo si el número de palillos n en el tablero no es n = 4k + 1, para cualquier k Z, k>0.

Que haya una estrategia en este caso significa que habrá una regla para decidir cuántos palillos quitar en cada turno si quedan n palillos en el tablero. Probaremos que si n = 4k + 1 el jugador 2 tiene una estrategia a su alcance que le permitirá forzar la derrota del jugador 1, y que en caso contrario el jugador 1 será el que tenga a su alcance una estrategia que le llevará a la victoria. Por lo tanto, el jugador 1 no podría evitar su derrota si quedan 1, 5, 9... palillos sobre el tablero, mientras que con otras cantidades de palillos sí podrá forzar la derrota del jugador 2.

Para la prueba usaremos el principio de inducción fuerte:

Hipótesis de inducción

Si para algún k N se tiene que n = 4k + 1, el jugador que mueve primero pierde; Si para algún k N se tiene que n = 4k, o n = 4k + 2, o n = 4k + 3, entonces el primer jugador gana. Estos 4 casos son exhaustivos y cubren todos los valores posibles de n.

Caso base

Caso n=1. En este caso el primer jugador no tiene otra eleccción que coger el único palillo sobre el tablero y perder el juego. Por tanto el teorema es cierto para el caso base.

Caso inductivo fuerte

Suponemos que la hipótesis de inducción es cierta para cualquier número de palillos entre 1 y n, (siendo n>1) vamos a comprobar que también se cumple para el caso n + 1. En este caso hay 4 posibilidades.

1. n + 1 = 4k + 1: Comprobemos que el primer jugador pierde. Como el caso base n=1 ya está verificado, podemos suponer que n + 1 > 5. El primer jugador puede escoger quitar 1, 2 o 3 palillos. Si quita un palillo, entonces quedarán n = 4k palillos para el jugador dos, y según la hipótesis de inducción fuerte, éste tendrá una estrategia ganadora y el jugador uno perderá.

Similarmente, si el primer jugador quita dos palillos, entonces quedarán 4k-1 = 4(k-1)+3 palillos para el jugador dos. De nuevo como hemos supuesto que se cumple la hipótesis de induccción para esta cantidad de palillos (menor que n+1), el jugador dos tendrá una estrategia ganadora y el jugador uno perderá. Igualmente le ocurrirá si decide quitar tres palillos y dejar 4k-2 = 4(k-1)+2 al jugador dos.

2. n + 1 = 4k: Demostremos que el primer jugador puede ganar de forma segura. Si el primer jugador quita 3 palillos entonces quedarán 4k-3 = 4(k - 1) + 1 palillos para el segundo jugador, y por la hipótesis inductiva fuerte el segundo jugador perderá.

3. n + 1 = 4k + 2: El primer jugador puede ganar de forma segura. Si el jugador uno quita 1 palillo entonces quedarán 4k+1 para el jugador dos, y por lo tanto el segundo jugador perderá igual que en el caso anterior.

4. n + 1 = 4k + 3: El primer jugador puede ganar de forma segura. Si el jugador uno quita 2 palillos entonces quedarán 4k+1 para el jugador dos, y por lo tanto el segundo jugador perderá, igual que en los dos últimos casos anteriores.

De esta forma vemos que se cumple la hipótesis para el caso n +1 también y queda demostrado el teorema.

Proponemos a algún lector animoso la tarea de hacer un programita que juegue a esta versión del Nim utilizando esta estrategia ganadora aquí demostrada. Si por ejemplo se deja elegir al jugador quién moverá primero y a cambio el programa decide después el número de palillos iniciales (o al revés), siempre podrá ganar el programa al oponente humano...

 

 

Vistas: 2087 | Agregado por: AbacoAzteca
Total de comentarios: 0
ComForm">
avatar