Newsgroup: it.hobby.enigmi
Titolo: Nim: Variante

Avete presente il gioco del Nim, in cui ci sono varie file di fiammiferi, e
due giocatori si alternano a rimuovere un numero qualunque di fiammiferi
purché sulla stessa fila? La strategia vincente è molto nota, ma esiste una
variante per cui i fiammiferi rimossi devono essere tutti adiacenti: in tal
caso qual è la strategia? Non so se il problema è già stato risolto oppure
no, magari è una cosa complicatissima, ma ci si può provare...
Ciao
Andrea

Andrea Artesiani wrote:

Ciao Andrea,
Secondo me non cambia nulla.
Come noto nel Nim classico, per sapere se una configurazione e' sicura, si 
calcola il numero di Sprague-Grundy, facendo la somma binaria Nim (cioe' 
senza riporto) delle varie righe. La posizione e' sicura se la somma Nim e' =0.
Un modo piu' pratico per calcolare detto numero, e' quello di esprimere 
ogni colonna come somma di potenze di due = 1,2,4,8... e poi cancellare 
coppie di potenze uguali. La somma di cio' che resta e' quella cercata.
Faccio un esempio. Iniziamo con un gioco formato da 3 linee rispettivamente 
di 3,5,7:
    III      = 1+2
   IIIII      = 1+4
 IIIIIII    = 1+2+4
Eliminando le coppie 11, 22, 44, resta Nim=1, se e' il mio turno posso 
portare la posizione in mio favore togliendo un fiammifero da una qualunque 
delle tre righe, per esempio la prima lasciando:
    II
   IIIII
  IIIIIII
Vediamo una mossa possibile dell'avversario nel modo classico e nella 
variante da te proposta.
Modo classico.
Il mio avversario toglie 2 fiammiferi dalla linea di sette lasciandomi 
2,5,5, col solito modo calcolo in numero Nim=2 (si puo' facilmente fare a 
mente ignorando le 2 file uguali)
   II     = 2
  IIIII   = 1+4
  IIIII   = 1+4
ed io riporto il gioco a mio vantaggio, togliendo ad es. la prima fila.
Variante. Il mio avversario toglie 2 fiammiferi dal centro della fila di 7 
lasciandomi 2,5,2,3. E' evidente che questa configurazione ha lo stesso 
valore Nim della precedente, e con la stessa mossa (via la prima fila) 
riprendo il vantaggio.
Dal primo momento che togliedo da una parte o dal centro di una fila, il 
valore totale non cambia, i due modi di giocare sembrano identici.
ciao dario

 fila) riprendo il vantaggio.
Perché dici che il valore Nim è lo stesso? Visto che la fila da 7 è stata
spezzata è come avere quattro file: da 2,5,2,3 la cui somma nim (cioè lo
xor) è 6. Però è vero che in ogni caso a partire da una configurazione
perdente non è possibile, neanche spezzando in due una riga, lasciare lo
xor a 0. Per cui alla fine la regola dello xor funziona ancora.
Ciao
Andrea

 xor a 0. Per cui alla fine la regola dello xor funziona ancora.
Scusa, ho pasticciato nell'esposizione.
Ho fatto un buon numero di prove per convincermi che la regola rimane la 
stessa, vedo che anche tu lo confermi.
ciao

...

Basta dimostrare che se xor=0 non c'è modo di lasciarlo a 0, neanche
prendendo i fiammiferi dal centro di una riga: se questo è vero chi trova
lo xor<>0 gioca con la strategia del vecchio nim, e l'avversario è
costretto a perdere. Vediamo allora di dimostrare che date n righe
a1,a2...an con xor(a1,a2...,an)=0 non è possibile vincere neanche spezzando
una riga in due. Supponiamo di prendere p gettoni dalla riga a1, lasciando
due zone da k e a1-k-p gettoni: le due zone disgiunte equivalgono a due
righe distinte secondo le vecchie regole perciò:
Date le righe a1..an con xor(a1,a2..an)=0 => a1=xor(a2..an) [1]
Prendendo p monete da a1, lasciandone k prima e a1-k-p dopo
se fosse ancora xor=0 avremmo:
0=xor(k,a1-k-p,a2..an)=xor(k,a1-k-p,a1) (dalla [1])
=> a1-k-p=xor(a1,k) => p=a1-k-xor(a1,k)
però xor(a1,k)>=a1-k => p<=0 , che è impossibile.
vediamo perché xor(a1,k)>=a1-k :
xor(0,0)=0=0-0
xor(1,0)=1=1-0 i primi tre casi vedono lo xor uguale alla differenza
xor(1,1)=0=1-1
xor(0,1)=1=2+(0-1) qui lo xor vale 2+ la differenza
pertanto: xor(a1,k)=a1-k+(alcuni 2 dove occorre) => xor(a1,k)>=a1-k
Ciao
Andrea