Nim

Disambiguazione – Se stai cercando altri significati, vedi NIM.

Il nim è un gioco per due giocatori.

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, ma senza modificare le altre pile. Vince chi toglie l'ultimo elemento presente sul campo di gara. Non è possibile passare (saltare la mossa).

Esiste anche una variante chiamata Marienbad, dal film L'anno scorso a Marienbad di Alain Resnais, nel quale veniva giocata dal protagonista. In questa variante chi toglie l'ultimo elemento perde.

Il nim è divenuto piuttosto famoso perché ha una strategia di vittoria semplice (ha classe di complessità L), 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. 10₂ + 11₂ = 101₂) ma tralasciando i riporti. Questo tipo di somma, considerando i numeri cifra per cifra, corrisponde alla disgiunzione esclusiva, o all'addizione nel campo finito ${\displaystyle \mathbb {F} _{2}}$. In teoria dei giochi, proprio per il suo uso in questa strategia, viene anche detta somma nim. Questa caratteristica fece si che, già nel 1951, la ditta inglese Ferranti riuscisse a presentare il Nimrod, uno dei primissimi dispositivi elettronici programmati per giocare.

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 (e viceversa), mentre è impossibile ottenere una posizione sicura partendo da una configurazione sicura.

Pila 1: 3 elementi       o o o Pila 2: 4 elementi      o o o o Pila 3: 5 elementi     o o o o o   310 = 0112 410 = 1002 510 = 1012     0 1 1 + 1 0 0 + 1 0 1 -------   0 1 0   

La somma non dà zero, quindi la posizione è insicura.

Una mossa vincente deve portare la somma nim a zero. Questo si può fare modificando il primo addendo in modo da "cancellare" l'1 del secondo posto. In pratica, si porta la pila 1 da 3 elementi a 1:

Pila 1: 1 elemento         o Pila 2: 4 elementi      o o o o Pila 3: 5 elementi     o o o o o   110 = 0012 410 = 1002 510 = 1012      0 0 1 +  1 0 0 +  1 0 1 --------    0 0 0   

La posizione è ora sicura. L'avversario, adesso, non potrà in nessun modo muovere senza incappare in una posizione insicura.

• Martin Gardner, Enigmi e giochi matematici, BUR 2001.

• Wikimedia Commons contiene immagini o altri file su nim

• (EN) nim, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Nim, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica