Alice e Bob giocano a questo gioco: inizialmente ci sono 3 colonne di monete, con $n_1,n_2,n_3$ monete, in modo tale che valga $n_1\le n_2\le n_3$; inizia Alice. A turno Alice e Bob possono fare una delle seguenti mosse, a condizione che rimanga vera la relazione $n_1\le n_2\le n_3$ dopo aver effettuato la mossa:
$\bullet$ Spostare $n\ge1$ monete dalla $k$-esima colonna alla $k+1$-esima (con $k=1,2$)
$\bullet$ Togliere da due colonne adiacenti $n\ge1$ monete
Perde chi non può più muovere.
Determinare, se esiste, la strategia vincente e per quali configurazioni di partenza vince Bob, se entrambi giocano al meglio.
Spero non sia troppo conosciuto...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
In pratica uno non può più muovere quando si ritrova 0,0,x. Questo perchè se la prima colonna e la seconda colonna hanno monete, si può applicare la seconda mossa sulle prime due colonne. Se invece la prima colonna ha 0 monete, ma la seconda colonna ha un numero di monete diverso da 0, si possono spostare le monete della seconda colonna sulla terza colonna. Rimane il caso in cui sia la prima colonna, sia la seconda hanno 0 monete, e in questo caso non si può applicare nessuna delle due mosse.
Da quanto ho capito la strategia sta nel fatto che il primo giocatore deve sempre fare in modo di lasciare all'avversario una situazione del tipo x,2x, qualcosa. Ovvero deve sempre fare in modo che al termine del suo turno la seconda colonna abbia il doppio delle monete della prima colonna.
Si verifica che il secondo giocatore, qualunque mossa faccia, non può fare in modo di ri-passare al primo giocatore una situazione del tipo x,2x,qualcosa.. Questo perchè se applica la prima mossa alle prime due colonne, il valore della prima diminuisce e quella della seconda aumenta, quindi non sarà il doppio della prima, se applica la seconda mossa alle prime due colonne, diminuisce entrambe le colonne dello stesso valore, e quindi la seconda colonna avrà più del doppio delle monete della prima. Se invece applica le mosse tra le seconda e la terza colonna diminuisce il numero di monete della seconda colonna che sarà meno del doppio della prima.
Il primo giocatore potrà di nuovo fare in modo che al termine del suo turno la seconda colonna abbia il doppio delle monete della prima.
Infatti se la seconda colonna ha più del doppio delle monete della prima, gli basta spostare quelle in eccesso sulla terza colonna. Se invece la seconda colonna ha meno del doppio delle monete della prima, detta $d$ la differenza di monete tra la seconda e la prima colonna si ha che $d$ è minore delle monete della prima colonna. Quindi applicando la seconda mossa lascerà $d$ monete sulla prima colonna e $2d$ monete sulla seconda.
Inevitabilmente alla fine il secondo giocatore si troverà nella situazione 0,0,x (0 è il doppio di 0) e quindi perderà.
Viceversa se all'inizio della partita vi è una configurazione in cui la seconda colonna ha il doppio delle monete della prima sarà il secondo giocatore a vincere, applicando la stessa strategia.
Quindi ricapitolando: se all'inizio la seconda colonna ha il doppio delle monete della prima vince il secondo giocatore, altrimenti vince il primo.
Piccolo bonus: cosa cambierebbe se $n$ dovesse essere necessariamente dispari?
Nel bonus $n$ è il numero di monete in ogni colonna? Ovvero tutte le colonne devono avere un numero dispari di monete?
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
