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

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...