02. Nim

Il gioco del Nim classico

Il gioco del Nim è uno dei giochi matematici più vecchi e più intriganti oggi conosciuti.

Il gioco si sviluppa con un insieme di elementi tutti uguali tra loro, ad esempio delle monete.

Tali elementi sono organizzati in pile, ciascuna con una certa altezza.

In ogni mossa il giocatore di turno può rimuovere da una pila a scelta un numero qualsiasi di elementi (al minimo uno, al massimo tutti gli elementi della pila).

Nella versione classica vince il giocatore che rimuove l’ultimo elemento.

Strategia

Il Nim è divenuto piuttosto famoso perché ha una strategia di vittoria semplice, facilmente utilizzabile come esempio nella teoria dei giochi.

La regola pratica è la seguente:

• Scrivere in binario il numero dei pezzi che si trovano in ogni pila;

• Mettere in colonna i numeri binari;

• Contare quanti "1" compaiono in ogni colonna;

• Ad ogni mossa bisogna fare in modo di lasciare all'avversario una configurazione con un numero pari di 1 in ogni colonna (stato sicuro).

Se si parte con una situazione in cui l'ultima condizione non è rispettata, allora il giocatore di turno ha sempre la possibilità di passare ad uno stato sicuro e di vincere con certezza la partita.

Esempio:

Pila 1 - 8 elementi: 1000

Pila 2 - 6 elementi: 0110

Pila 3 - 5 elementi: 0101

----

DPDD

In questa configurazione mettendo in colonna i numeri binari risulta che ben 3 colonne hanno un numero dispari di 1 (le colonne sono contrassegnate con la D). Quindi la configurazione è favorevole ed è possibile vincere la partita con certezza.

Una mossa possibile è quella di sottrarre monete dalla prima Pila in modo che la numerazione binaria risulti 0011 (che corrisponde al numero 3). Occorre quindi lasciare 3 monete nella prima Pila.

Pila 1 - 3 elementi: 0011

Pila 2 - 6 elementi: 0110

Pila 3 - 5 elementi: 0101

----

PPPP

Il giocatore di turno, partendo da questa configurazione non ha la possibilità di mantenere la parità su tutte le colonne. Tutte le mosse sono quindi perdenti.

Può ad esempio rimuovere ancora un elemento dalla prima pila.

Pila 1 - 2 elementi: 0010

Pila 2 - 6 elementi: 0110

Pila 3 - 5 elementi: 0101

----

PPPD

Partendo da questa configurazione è ancora possibile raggiungere la parità su tutte le colonne, ad esempio rimuovendo un elemento dalla terza pila.

Pila 1 - 1 elementi: 0010

Pila 2 - 6 elementi: 0110

Pila 3 - 5 elementi: 0100

----

PPPP

Si continua con la stessa tecnica fino alla fine della partita che inevitabilmente sarà vinta dal primo giocatore.

Marienbad

Si tratta di un Nim inverso (chi prende per ultimo perde!) con un preciso numero di elementi in ciascuna pila.

Il gioco fu reso famoso dal film L'anno scorso a Marienbad (1961), nel quale il protagonista vince tutte le partite che gioca (vedi il trailer al minuto 2:19).

Per la cronaca, Marienbad (Bagni di Maria, pronuncia Ma-rì-en-bad) è una cittadina della Repubblica Ceca a ridosso del confine con la Germania.

Normalmente si gioca con quattro file di fiammiferi (o altri oggetti) formate rispettivamente da 1-3-5-7 elementi, disposte come in figura. E' possibile giocare on-line cliccando sul link.

In questo caso la strategia è un po' più articolata del Nim classico:

• si procede normalmente cercando di raggiungere una posizione sicura (cioè tale per cui il numero di uno presenti in ogni colonna che rappresenta la nuova configurazione in binario sia pari) e di mantenerla in tutte le mani successive fin quando esistono almeno due file con più fiammiferi;

• se esiste una sola fila con più fiammiferi e il numero di file è pari occorre eliminare del tutto la fila;

• se esiste una sola fila con più fiammiferi e il numero di file è dispari occorre lasciare un solo fiammifero nella fila.

Quando restano solo file con un fiammifero il gioco va da sé.

Inizialmente esiste una strategia vincente per il giocatore di turno se la configurazione non è "sicura" (cioè se almeno in una colonna che rappresenta la configurazione iniziale in binario, il numero di uno non è pari). Nella configurazione classica 1-3-5-7 il primo che gioca perde (se l'avversario opera in modo ottimale)!

Consideriamo ad esempio la seguente scenario:

Fila 1 - 1 elemento: 001

Fila 2 - 3 elementi: 011

Fila 3 - 5 elementi: 101

Fila 4 - 6 elementi: 110

---

PPD

In questa configurazione mettendo in colonna i numeri binari risulta che una colonna ha un numero dispari di 1 (la colonna è contrassegnata con la D). Quindi la configurazione è favorevole per chi è di turno ed è possibile vincere la partita con certezza.

Una mossa possibile è quella di sottrarre fiammiferi dalla seconda fila in modo che la numerazione binaria risulti 010 (che corrisponde al numero 2). Occorre quindi lasciare 2 fiammiferi nella seconda fila.

Fila 1 - 1 elemento: 001

Fila 2 - 2 elementi: 010

Fila 3 - 5 elementi: 101

Fila 4 - 6 elementi: 110

---

PPP

L'avversario non ha la possibilità di rispondere con una mossa vincente e qualsiasi scelta effettuerà consegnerà una configurazione favorevole all'altro giocatore.

Sito: 7ecnologie

Sezione: 01. Problem Solving

Capitolo: 05. Giochi di strategia

Paragrafo: 02. Nim

Indice dei capitoli: 00. Risorse - 01. Problemi di attenzione - 02. Problemi di logica - 03. Pensiero laterale - 04. Paradossi - 05. Giochi di strategia

Indice dei paragrafi: 01. Strike and balls - 02. Nim - 03. Hex