Soluzione all'enigma 41, proposto da Michela E. il 2 maggio 2005

Michela e Stefano ogni giorno si fanno avvelenare...ehm...decidono di pranzare insieme alla mensa della facoltà'. La mensa è frequentata da molti studenti per cui spesso le code sono piuttosto lunghe. A volte quindi i due amici, onde evitare di lasciare che Michela chiacchieri per tutto il tempo della coda, decidono di ingannare il tempo giocando al seguente gioco, per il quale coinvolgono anche il loro amico Cesare anche lui in coda (che anche lui si lascia coinvolgere volentieri pur di non lasciare chiacchierare Michela oltre misura!). Il gioco funziona così:
Cesare estrae dal proprio portafogli alcune monete, le divide in due pile e tiene nella mano destra una pila di m monete e nella mano sinistra una pila di n monete. Michela e Stefano possono scegliere a turno una delle seguenti mosse:
- prendere una moneta da una delle due pile;
- prendere una moneta da ciascuna delle due pile;
- spostare una moneta da una pila all'altra.
Perde chi non può più muovere. Comincia Michela (perché Stefano è cavaliere).
Determinare in funzione dei numeri n ed m se uno dei due giocatori ha una strategia vincente e in caso affermativo specificare di quale giocatore si tratta. (alla fine del gioco tutte le monete vengono restituite a Cesare che altrimenti digiuna! :-))

Soluzioni

Ecco la soluzione data da Fulvia:

Secondo i miei ragionamenti non  o sempre il 1 o sempre il 2 giocatore a vincere, ma dipende dalla situazione iniziale, cio dai valori di m e di n in partenza (o eventualmente da un certo punto in poi, se uno dei due giocatori "sbaglia" la sua mossa).

La conclusione generale a cui sono giunta  che:
1) se m e n sono entrambi dispari oppure se uno  dispari e l'altro pari (quindi se almeno uno dei due  dispari) vince il 1 giocatore,
2) se m e n sono entrambi pari vince il 2 giocatore.

In pratica se indico con D il caso in cui in cui la pila abbia un numero dispari di monete e con P il caso in cui in cui la pila abbia un numero pari di monete, si pu schematizzare cos (la prima lettera si riferisce alla pila con m monete, la seconda lettera alla pila con n monete):
1) D D oppure P D oppure D P => vince il 1 giocatore
2) P P => vince il 2 giocatore

La strategia vincente  la seguente:
1) Se si ha D D oppure P D oppure D P, il 1 giocatore, ad ogni suo turno, deve prendere una moneta dalla pila che contiene un numero dispari di monete (se sono una dispari e una pari) oppure prendere una moneta da ciascuna delle due pile (se sono entrambe dispari) oppure, in alternativa, spostare una moneta da una pila all'altra (sempre solo se sono entrambe dispari) in modo da lasciare all'avversario entrambe le pile con un numero pari di monete: P P. A questo punto, qualunque mossa far il 2 giocatore, si torner ad avere almeno una pila con numero dispari di monete cio si avr di nuovo D D oppure P D oppure D P e si potr iterare il procedimento finché il 1 giocatore avr una delle seguenti situazioni numeriche: 1 1 oppure 0 1 oppure 1 0. A questo punto prendendo una moneta da entrambe le pile oppure da una sola, lascer all'avversario zero monete in entrambe le pile: 0 0. Quindi vincer il 1 giocatore.
2) Se invece si ha P P, la situazione  ribaltata rispetto a prima: il 1 giocatore, qualunque mossa faccia, passa da P P alla situazione D D oppure P D oppure D P che   vantaggiosa per il 2 giocatore (non sto a ripetere tutto il discorso, perch   inutile).

Ti propongo la spiegazione dettagliata nel caso in cui in partenza m sia dispari e n pari (non riporto invece la spiegazione per gli altri casi (m dispari con n dispari; m pari con n dispari; m pari con n pari) solo perch sarebbe ripetitivo e noiosissimo ...).

Situazione iniziale m dispari e n pari => D P

Il 1 giocatore toglie una moneta dalla pila dispari e diventano entrambe pari => P P

Il 2 giocatore ha 5 mosse possibili:
1) sposta una moneta dalla 1 alla 2 pila => D D
2) sposta una moneta dalla 2 alla 1 pila => D D
3) toglie una moneta dalla 1 pila => D P
4) toglie una moneta dalla 2 pila => P D
5) toglie una moneta da entrambe le pile => D D

Il 1 giocatore ha, in base alla mossa del 2, le seguenti possibilit:
nei casi 1), 2) e 5) (avendo cio D D) toglie una moneta da entrambe le
pile => P P
(oppure, in alternativa, sposta una moneta da una pila all'altra ottenendo
ancora P P, ma in questo modo ... si va per le lunghe!)
nel caso 3)(avendo cio D P) toglie una moneta dalla 1 pila => P P
nel caso 4)(avendo cio P D) toglie una moneta dalla 2 pila => P P
Come si vede, in tutti i casi il 1 giocatore ripresenta al 2 la situazione
P P come prima.

Il 2 giocatore si ritrova ancora a scegliere una mossa tra le 5 viste
prima, ecc. Cio si va avanti procedendo nello stesso modo, finch
decrementando via via il numero delle monete dalle due pile, al 1
giocatore rimane una di queste possibili scelte:
a) una moneta in entrambe le pile cio 1 1
b) solo pi una moneta nella 1 pila cio 1 0
c) solo pi una moneta nella 2 pila cio 0 1

Il 1 giocatore a questo punto vince perch a seconda dei casi muove cos:
a) prende una moneta da entrambe le pile => 0 0
b) prende una moneta dalla 1 pila => 0 0
c) prende una moneta dalla 2 pila => 0 0

Al 2 giocatore non rimangono pi monete e non pu pi muovere.

**********************************

Soluzione di Stefano

**********************************


Dunque dunque...
Intanto, dopo attenta analisi, come gia' sai ho deciso che non giocherò mai a questo gioco contro di te, visto che mi toccherebbe di perdere 3 volte su quattro (ipotizzando che i numeri m ed n siano scelti casualmente).
Comunque, la mia soluzione e' la seguente: se m ed n sono entrambi pari, allora Stefano ha una strategia vincente e quindi, ipotizzando sempre che i giocatori siano razionali, vince; in tutti gli altri casi e' Michela ad avere una strategia vincente.

Come lo si scopre? Beh, io l'ho dimostrato cosi'.
Intanto e' evidente che se in mano a Cesare restano (0,0) monete il giocatore di turno non puo' piu' muovere e quindi ha perso, e questo e' l'unico caso possibile, infatti se c'e' almeno una moneta il giocatore di turno puo' sempre toglierla.

Dimostriamo:
(1) presi comunque a e b in N, la posizione di gioco (2a,2b) e' perdente per il giocatore che si trova a dover muovere. Per induzione su a:
I) a=0 ovvero (0,2b)... e' facile verificarlo.
II) a-1 ==> a, ovvero assumo l'ipotesi induttiva
(*) (2a-2,b) e' perdente per ogni b

Ora procedo per induzione su b.
II-I) b=0 ovvero (2a,0)... e' facile come prima.
II-II) b-1 ==> b, ovvero assumo l'ulteriore ipotesi induttiva
(**) (2a,2b-2) e' perdente (ora a e' fissato, a differenza del b di (*))

Partendo dalla posizione (2a,2b) le possibili mosse del giocatore di turno sono:
(2a-1,2b)
(2a,2b-1)
(2a-1,2b-1)
(2a+1,2b-1)
(2a-1,2b+1)

Ma da queste posizioni l'altro giocatore ha sempre una mossa vincente che puo' fare, infatti:
(2a-1,2b) --> (2a-2,2b) perdente per (*)
(2a,2b-1) --> (2a,2b-2) perdente per (**)
(2a-1,2b-1) --> (2a-2,2b-2) perdente per (*)
(2a+1,2b-1) --> (2a,2b-2) perdente per (**)
(2a-1,2b+1) --> (2a-2,2b) perdente per (*)

CVD

Ora il caso generale: i due numeri m,n possono essere o pari o dispari, dunque distinguiamo 3 casi:
(pari,pari) --> Per (1) questa e' una posizione perdente per il giocatore di turno, quindi per Michela che deve cominciare il gioco.
(pari,dispari) --> Michela ha una strategia vincente: le basta togliere una moneta dalla colonna dispari per ottenere (pari,pari) e per (1) questa e' una posizione perdente per Stefano, a cui spetta muovere.
(dispari,dispari) --> Michela ha una strategia vincente: le basta togliere una monteta da ciascuna delle colonne per ottenere (pari,pari) e per (1) questa e' una posizione perdente per Stefano, a cui spetta muovere.
E questo e' quanto.