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à.
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.