Soluzione all'enigma 68, proposto da Michela E. il 27 marzo 2006

Forse vi ricorderete che io sono emiliana (sono nata in provincia di Piacenza) e come tutte (o quasi) le donne emiliane sono appassionata di cucina. Mi piace cucinare e proporre ai miei ospiti i vari piatti tipici della mia zona, a cominciare dai primi...lasagne, tortellini, crespelle. Fatto sta che durante i nostri pranzi in mensa mi è venuto spesso spontaneo commentare di fronte a un piatto poco invitante: "Ah, io di sicuro lo saprei fare meglio!" E dillo oggi, e dillo domani...ai miei amici Mauro e Valerio è venuta la curiosità di vedermi all'opera e così mi hanno gentilmente invitata (costretta? forzata?) a organizzare una cena a casa di Valerio in cui avrei cucinato le mie specialità solo per loro. E così l'8 marzo scorso (festa della donna) mi sono recata dopo pranzo a casa di Valerio per cucinare. Ho fatto le lasagne ma proprio dall'inizio, a partire dal soffritto del sugo!! L'unica cosa che mi sono concessa è di comprare le sfoglie di pasta già pronte (fare la pasta fatta in casa sarebbe stato veramente troppo lungo!) Ma per il resto ho fatto tutto da sola, nessuno dei miei amici si è affrettato a darmi una mano! Non solo, quando verso sera, esasperata e piena di farina ho chiesto ai miei amici almeno di darmi una mano a mettere un po' di ordine..quelli si sono messi a giocare! Incredibile, vero? (e infatti chi ci crede???) Ma vi posso assicurare che Mauro e Valerio hanno iniziato il seguente gioco.
Hanno preso le sfoglie di pasta per le lasagne che avevo avanzato (ed erano rimaste in tutto ben 2006 sfoglie! Come recitava una nota pubblicità: "le nostre porzioni sono sempre molto generose"!), le hanno disposte sul tavolo e poi a turno i due amici dovevano togliere dal tavolo un numero di sfoglie a loro scelta, purché maggiore o uguale a uno, e minore o uguale alla metà del numero di sfoglie che in quel momento erano sul tavolo. Il giocatore che lasciava sul tavolo una sola sfoglia perdeva. Ovviamente Mauro ha iniziato per primo a giocare (non sia mai detto che lasci a Valerio questo privilegio). A voi chiedo: determinare per quale dei due giocatori esiste una strategia vincente e descrivere tale strategia.
P.S. La cena è stata un successo, ho ricevuto ben due proposte di matrimonio!!! Però, passare così la festa della donna...

Soluzione (di Michela)
La strategia vincente si può determinare procedendo a ritroso.Chi lascia una sola sfoglia sul tavolo perde. Chi ne lascia due vince, perché costringe l’altro giocatore a lasciarne una sola. Chi ne lascia 3 o 4 perde, perché alla mossa successiva l’altro potrà lasciarne due. Chi ne lascia 5 invece vince, perché costringe l’altro a lasciarne 3 o 4, che abbiamo visto essere mosse perdenti. Analogamente si vede che lasciarne 6, 7, 8, 9 o 10 è una mossa perdente (permette all’altro di lasciarne 5), mentre lasciarne 11 è vincente.
Questo ragionamento si può ripetere all’infinito: se lasciare k sfoglie è una mossa vincente, allora lasciarne un numero compreso tra k+1 e 2 k (estremi inclusi) è perdente, mentre lasciarne 2k + 1 è vincente. In conclusione i “numeri vincenti” si possono facilmente determinare partendo da due e sfruttando per ricorrenza il fatto appena osservato che se k è vincente, allora anche 2k +1 è vincente. I numeri vincenti minori di 1999 sono pertanto: 2, 5, 11, 23, 47, 95, 191, 383, 767, 1535. Mauro quindi può vincere seguendo questa strategia: alla prima mossa lascia sul tavolo 1535 sfoglie, la seconda volta che tocca a lui ne lascia 767, la terza volta 383 e così via. Procedendo in questo modo la decima volta che tocca a lui ne lascierà sul tavolo solo 2 e alla mossa successiva Valerio perderà.

Soluzione (di Anita)
Sia G_n il gioco analogo a quello da te proposto ma in cui le lasagne in gioco sono n.
Sia x_i la succesione definita da x_i = 3(2^i)-1. Si ha:
Proposizione. A gioco corretto il primo giocatore di G_n perde se e solo se n è della forma x_i per qualche i?0.
Ciò è banalmente vero nel caso i=0: se ho due lasagne l’unica cosa che può fare il primo giocatore è togliere una lasagna. Ne resta solo una e quindi perde.
Supponiamo che la proposizione sia vera per ogni n ? x_i e mostriamo che lo è per ogni n ? x_{i+1}.
Se x_i < n < x_{i+1}, la mossa corretta del primo giocatore è togliere n-x_i lasagne (si noti che n-x_i è effettivamente non superiore ad n/2 poiché in caso contrario avremmo n > 2x_i ossia n ? x_{i+1} contro l’ipotesi). A questo punto infatti, il secondo giocatore trovandosi nelle stesse condizioni di un “primo giocatore” di G_{x_i}, perde per ipotesi induttiva. Infine, sia n = x_{i+1}. Qualunque sia il numero di lasagne tolto dal primo giocatore, il numero r di lasagne rimaste è nell’intervallo aperto (x_i,x_{i+1}). Quindi il secondo giocatore, trovandosi nelle stesse condizioni di un “primo giocatore” di un G_r, vince per quanto visto sopra.
C.d.d.
Concludendo Mauro vince togliendo 471 lasagne:
471 < 2006/2;
2006 - 471 = 3(2^9) - 1.

Soluzione (di Stefano)
Dunque dunque...
Intanto un esordio da matematico: si tratta di un gioco finito ad informazione perfetta, pertanto sicuramente *esiste* per uno dei due giocatori una strategia vincente, ce lo garantisce un teorema "alla Zermelo".
Proviamo a determinarla. Intanto indichiamo con 1 e 2 i due giocatori, scriviamo:
n_i := 3 x 2^(i-1) -1
e cominciamo a dimostrare i seguenti fatti:
a) Se il numero N di lasagne sul tavolo è della forma n_i per qualche i, allora chi muove necessariamente perde (ovvero il secondo giocatore a muovere ha sempre una strategia vincente).
Dimostrazione. Per induzione su i >= 1.
i=1) n_i=2. Il primo giocatore deve necessariamente togliere 1 sfoglia, quindi perde perché ne lascia soltanto una sul tavolo, ovvero 2 vince.
i-1 ==> i) Il numero n_i è dispari, pertanto il numero massimo di sfoglie che il giocatore 1 può togliere è:
(n_i - 1) / 2 = ... = n_(i-1)
e quindi il numero minimo di sfoglie che restano sul tavolo dopo che 1 ha mosso è pari a
n_i - n_(i-1) = ... = 3 x 2^(i-2) = n_(i-1) + 1 > n_(i-1).
(il numero massimo di sfoglie è, ovviamente, n_i - 1)
Pertanto, qualsiasi mossa faccia 1, per 2 è sufficiente togliere un numero di sfoglie tale da lasciare 1 con n_(i-1) sfoglie sul tavolo, e a questo punto 1 perde per l'ipotesi indutiva. QED.
b) Se il numero di sfoglie sul tavolo non è della forma n_i per qualche i, allora il primo giocatore che muove ha sempre una strategia vincente.
Dimostrazione. Segue immediatamente da a) osservando che ad 1) basta rimuovere un numero di sfoglie tale da lasciare sul tavolo un numero di sfoglie della forma n_i per un opportuno i, e questo può sempre farlo perché tra N-(N-1)/2 e N c'è sempre un numero della forma n_i. QED.
Poiché 2006 non è della forma n_i, per b) Mauro ha sempre una strategia vincente. In particolare la sua prima mossa dovrebbe essere
2006 --->  1535 = 3 x 2 ^ 9 - 1 = n_10
rimuovendo 471 sfoglie, e a questo punto per a) vince.

Soluzione (di Fulvia)
Secondo me esiste una strategia vincente e SUPPONENDO CHE ENTRAMBI LA CONOSCANO e GIOCHINO PER VINCERE, con 2006 sfoglie in partenza, la vittoria andrà a chi gioca per primo, quindi nel nostro caso a Mauro.
Il ragionamento che ho fatto è stato di percorre le mosse “al contrario”, cioè partendo dall’ultima e andando a ritroso, considerando le diverse possibilità.
Visto che il giocatore che lascia sul tavolo una sola sfoglia perde, chi si trova a giocare con le ultime 2 sfoglie PERDE sicuramente, perché è obbligato a toglierne una, lasciandone dunque una sola!
A questo punto del gioco la mossa vincente è lasciare all’avversario 2 sfoglie.
Allora chi gioca con 3 o 4 sfoglie vince sicuramente, perché togliendone rispettivamente 1 o 2 lascia l’avversario con 2 e in questo modo lo fa perdere.
Schematicamente, indicando con A e B i due giocatori:
A ha 2 sfoglie => ne toglie 1 => ne resta 1 => A PERDE
A ha 3 sfoglie => ne toglie 1 => ne restano 2 => B perde => A vince
A ha 4 sfoglie => ne toglie 2 => ne restano 2 => B perde => A vince
Se il giocatore ha 5 sfoglie (5=2+2+1=2*2+1) può scegliere di toglierne 1 o 2 (non 3=2+1, perché il numero deve essere minore o uguale alla metà del numero di sfoglie presenti, che è 5), ma in entrambi i casi PERDE:
A ha 5 sfoglie => ne toglie 1 => ne restano 4 => B ne toglie 2 => ne restano 2 => A PERDE
A ha 5 sfoglie => ne toglie 2 => ne restano 3 => B ne toglie 1 => ne restano 2 => A PERDE
In pratica a questo punto del gioco la mossa vincente è lasciare all’avversario 5 sfoglie.
Allora chi gioca con 6, 7, 8, 9 o 10 sfoglie vince sicuramente, perché può togliere un numero di sfoglie tale da lasciare l’avversario con 5 e in questo modo lo fa perdere.
Ragionando in modo analogo, se il giocatore resta con 11 sfoglie (11=5+5+1=2*5+1) non può toglierne più di 5 (non 6=5+1, perché il numero deve essere minore o uguale alla metà del numero di sfoglie presenti, che è 11) e pertanto qualunque mossa faccia, lascia l’avversario in condizione di vincere.
Dunque il giocatore che ha 11 sfoglie PERDE.
A questo punto del gioco la mossa vincente è lasciare all’avversario 11 sfoglie.
Generalizzando, PERDE chi resta con 2, 5, 11, 23, 47, 95, 191, 383, 767, 1535, 3071, … sfoglie o potremmo anche dire che vince chi lascia all’avversario sul tavolo 2, 5, 11, 23, 47, 95, 191, 383, 767, 1535, 3071, … sfoglie e può farlo solo chi NON ha sul tavolo 2, 5, 11, 23, 47, 95, 191, 383, 767, 1535, 3071, … sfoglie!
La successione di numeri si ottiene, ovviamente, in questo modo:
a_0=2
a_1= 2*a_0+1
a_2= 2*a_1+1

a_(n+1)= 2*a_n+1
In conclusione, visto che inizialmente ci sono 2006 sfoglie, il giocatore che gioca per primo può vincere, perché togliendo 471 sfoglie ne lascia all’avversario 1535 e, per quanto detto, quest’ultimo PERDE sicuramente.