Nim
Da Wikipedia, l'enciclopedia libera.
Il nim è un gioco matematico per due giocatori.
Indice |
[modifica] Regole
Si parte con una serie di pile contenenti un certo numero di elementi (il numero delle pile e degli elementi di ciascuna pila sono concordati a piacere tra i giocatori all'inizio della partita). I giocatori, a turno, tolgono da una qualsiasi pila un numero d'elementi a piacere, da uno a tutti. Vince chi toglie l'ultimo elemento presente sul campo di gara. Non è possibile passare (saltare la mossa).
Esiste anche una variante, secondo la quale chi toglie l'ultimo elemento perde.
[modifica] Strategia
Il nim è divenuto piuttosto famoso perché ha una strategia di vittoria semplice, facilmente utilizzabile come esempio in teoria dei giochi.
La strategia si basa sul calcolo binario, e precisamente su una particolare addizione per cifre della rappresentazione binaria del numero di elementi nelle pile: essa viene svolta come una normale somma (ma nel sistema binario, dove per es. 102 + 112 = 1012) ma tralasciando i riporti. Questo tipo di somma, considerando i numeri cifra per cifra, corrisponde alla disgiunzione esclusiva, o all'addizione nel campo finito
. In teoria dei giochi, proprio per il suo uso in questa strategia, viene anche detta somma nim.
Esempio
1010011 + 0100110 ------- = 1110101
La strategia del gioco si basa sulla distinzione tra posizioni (o configurazioni) sicure e insicure. Una configurazione si dice sicura se la somma nim delle rappresentazioni binarie degli elementi delle pile dà 0; altrimenti si dice insicura. La strategia vincente consiste nel lasciare all'avversario, ad ogni mossa, una configurazione sicura. È sempre possibile raggiungere una posizione sicura a partire da una insicura, mentre è impossibile farlo partendo da una configurazione sicura.
[modifica] Esempi
[modifica] Posizione
Pila 1: 3 elementi Pila 2: 4 elementi Pila 3: 5 elementi 310 = 0112 410 = 1002 510 = 1012 0 1 1 + 1 0 0 + 1 0 1 -------- 0 1 0 La posizione è insicura
[modifica] Strategia di gioco
Pila 1: 3 elementi Pila 2: 4 elementi Pila 3: 5 elementi 011 + 100 + 101 = 010 La posizione è insicura. Il giocatore A toglie 2 elementi dalla pila 1; 001 + 100 + 101 = 000 La posizione è sicura. Il giocatore B toglie 1 elemento dalla pila 2; 001 + 011 + 101 = 111 La posizione è insicura. Il giocatore A toglie 3 elementi dalla pila 3; 001 + 011 + 010 = 000 La posizione è sicura. Il giocatore B toglie 1 elemento dalla pila 1; 000 + 011 + 010 = 001 La posizione è insicura. Il giocatore A toglie 1 elemento dalla pila 2; 000 + 010 + 010 = 000 La posizione è sicura. Il giocatore B toglie 2 elementi dalla pila 2; 000 + 000 + 010 = 010 La posizione è insicura. Il giocatore A toglie 2 elemento dalla pila 3 e vince.
[modifica] Bibliografia
- M. Gardner, Enigmi e giochi matematici, BUR 2001
