I Cerini
Alberto e Barbara fanno il seguente gioco:
Su di un tavolo ci sono 1999 cerini: a turno ogni giocatore deve togliere dal tavolo un numero di cerini a sua scelta, purche maggiore o uguale ad uno, e minore o uguale alla meta del numero dei cerini che in quel momento sono sul tavolo. Il giocatore che lascia sul tavolo un solo cerino perde. Barbara e la prima a giocare.
Determinare per quale dei due giocatori esiste una strategia vincente e descrivere tale strategia.
Su di un tavolo ci sono 1999 cerini: a turno ogni giocatore deve togliere dal tavolo un numero di cerini a sua scelta, purche maggiore o uguale ad uno, e minore o uguale alla meta del numero dei cerini che in quel momento sono sul tavolo. Il giocatore che lascia sul tavolo un solo cerino perde. Barbara e la prima a giocare.
Determinare per quale dei due giocatori esiste una strategia vincente e descrivere tale strategia.
Risposte
Non sono sicuro della soluzione, ma azzardo
indipendentemente da ciò che fa Barbara, Alberto farà in modo che il numero di cerini resti dispari (diciamo che se B toglie una quantità pari, A farà lo stesso, se B toglie dispari, A idem)
A questo punto A dovrà fare in modo di far rimanere 5 cerini sul tavolo (ecco, qui devo pensare come sia possibile questo in generale...) e a quel punto semplici calcoli permettono di dire che A vince indipendentemente da quello che fa B. Intuitivamente mi è venuto spontaneo pensare che il secondo di mano sia il vincente perché vede ciò che fa il primo e agisce di conseguenza. A non può far rimanere 7 cerini, perché altrimenti B a quel punto ne toglie 2 ed è A a trovarsi nella situazione precedente (e chiaramente perderebbe). Idem A non può far rimanere 3 cerini perché B ne toglierebbe 1 e A pure e perderebbe.
Insomma, io credo che vincerà Alberto con la strategia sopra descritta (non proprio bene). Si tratta di provare per numeri piccoli e poi generalizzare.
indipendentemente da ciò che fa Barbara, Alberto farà in modo che il numero di cerini resti dispari (diciamo che se B toglie una quantità pari, A farà lo stesso, se B toglie dispari, A idem)
A questo punto A dovrà fare in modo di far rimanere 5 cerini sul tavolo (ecco, qui devo pensare come sia possibile questo in generale...) e a quel punto semplici calcoli permettono di dire che A vince indipendentemente da quello che fa B. Intuitivamente mi è venuto spontaneo pensare che il secondo di mano sia il vincente perché vede ciò che fa il primo e agisce di conseguenza. A non può far rimanere 7 cerini, perché altrimenti B a quel punto ne toglie 2 ed è A a trovarsi nella situazione precedente (e chiaramente perderebbe). Idem A non può far rimanere 3 cerini perché B ne toglierebbe 1 e A pure e perderebbe.
Insomma, io credo che vincerà Alberto con la strategia sopra descritta (non proprio bene). Si tratta di provare per numeri piccoli e poi generalizzare.
No,purtroppo la risposta non è corretta, e a questo punto, mi permetto di darti un consiglio.
Quando incontri problemi di questo tipo è sconsigliato procedere con una strategia che l'avversario può rifare su di te, mi spiego meglio
Questo punto non è corretto,perchè al turno dopo è come se Barbara cominciasse una nuova partita cercando di attuare la stessa strategia.
Ti faccio un altro esempio,stilizzando moltissimo un problema che ho fatto tempo fa:
"si possono togliere dal tavolo solo 2 o 3 gettoni,vince chi toglie l'ultimo gettone,comincia A,chi vince?"
chiaramente se A riuscisse a lasciare sul tavolo $5k$ gettoni avrebbe vinto,perchè al turno dopo B toglierà 2 o 3 gettoni , e A toglierà l'opposto in modo tale da far rimanere sempre un numero di gettoni multiplo di 5,arrivare a 5 e vincere.
Se il testo fosse stato come quello originale dei cerini, e io avessi cercato una strategia mettendo dentro i multipli di 5,avrei creato un pasticcio,perchè anche lui può lasciarmi multipli di 5, e perciò non ho un completo controllo della situazione,nessuno mi assicura la vittoria.
Spero di essere stato di aiuto e in ogni caso non voglio assolutamente fare la figura di quello che sa più degli altri
Quando incontri problemi di questo tipo è sconsigliato procedere con una strategia che l'avversario può rifare su di te, mi spiego meglio
"marco9999":
indipendentemente da ciò che fa Barbara, Alberto farà in modo che il numero di cerini resti dispari (diciamo che se B toglie una quantità pari, A farà lo stesso, se B toglie dispari, A idem)
Questo punto non è corretto,perchè al turno dopo è come se Barbara cominciasse una nuova partita cercando di attuare la stessa strategia.
Ti faccio un altro esempio,stilizzando moltissimo un problema che ho fatto tempo fa:
"si possono togliere dal tavolo solo 2 o 3 gettoni,vince chi toglie l'ultimo gettone,comincia A,chi vince?"
chiaramente se A riuscisse a lasciare sul tavolo $5k$ gettoni avrebbe vinto,perchè al turno dopo B toglierà 2 o 3 gettoni , e A toglierà l'opposto in modo tale da far rimanere sempre un numero di gettoni multiplo di 5,arrivare a 5 e vincere.
Se il testo fosse stato come quello originale dei cerini, e io avessi cercato una strategia mettendo dentro i multipli di 5,avrei creato un pasticcio,perchè anche lui può lasciarmi multipli di 5, e perciò non ho un completo controllo della situazione,nessuno mi assicura la vittoria.
Spero di essere stato di aiuto e in ogni caso non voglio assolutamente fare la figura di quello che sa più degli altri
Non preoccuparti per quello (neanch'io ne so più di altri) e grazie dell'aiuto.
Effettivamente ora mi rendo conto che la strategia che ho descritto non ha alcun senso. Vale la pena pensarci un po' di più, se ho idee tornerò a scrivere
Effettivamente ora mi rendo conto che la strategia che ho descritto non ha alcun senso. Vale la pena pensarci un po' di più, se ho idee tornerò a scrivere
Andando per ricorrenza (e poi per induzione) si ricava che il secondo giocatore vince con gli $n$ (numero di cerini iniziali) del tipo:
[tex]3\cdot 2^k-1[/tex]. Questo è dovuto al fatto che con $n=2$ vince Alberto, di conseguenza se per un certo $n=x$ vince Alberto, con tutti gli $n$ che vanno da $x+1$ a $2x$ vince Barbara in quanto con la prima mossa le basta lasciare sul tavolo $x$ cerini e così facendo è come se Alberto cominciasse una nuova partita con $n=x$ dove si è verificato prima che vince il secondo che in questo caso sarebbe Barbara. Poi con $n=2x+1$ Barbara è costretta a lasciare un numero di cerini compreso tra $x+1$ e $2x$, quindi per quanto dimostrato prima vince Alberto.
Quindi Alberto vince con tutti e soli i numeri del tipo $2,5,11,23,47...$ e così via. E la formula che genera questi numeri è [tex]3\cdot 2^k-1[/tex].
$1999$ non è congruo a 2 modulo 3, quindi sicuramente non è tra i numeri per cui vince Alberto, quindi vince Barbara.
La strategia vincente consiste nel lasciare sul tavolo $1535$ che sarebbe $2^9\cdot 3-1$. Poi qualsiasi mossa fa Alberto, al turno dopo Barbara gli lascerà $2^8\cdot 3-1$ cerini e così via.. alla fine Barbara le gli lascia $2$ cerini, Alberto ne toglie 1 e vince Barbara.
[tex]3\cdot 2^k-1[/tex]. Questo è dovuto al fatto che con $n=2$ vince Alberto, di conseguenza se per un certo $n=x$ vince Alberto, con tutti gli $n$ che vanno da $x+1$ a $2x$ vince Barbara in quanto con la prima mossa le basta lasciare sul tavolo $x$ cerini e così facendo è come se Alberto cominciasse una nuova partita con $n=x$ dove si è verificato prima che vince il secondo che in questo caso sarebbe Barbara. Poi con $n=2x+1$ Barbara è costretta a lasciare un numero di cerini compreso tra $x+1$ e $2x$, quindi per quanto dimostrato prima vince Alberto.
Quindi Alberto vince con tutti e soli i numeri del tipo $2,5,11,23,47...$ e così via. E la formula che genera questi numeri è [tex]3\cdot 2^k-1[/tex].
$1999$ non è congruo a 2 modulo 3, quindi sicuramente non è tra i numeri per cui vince Alberto, quindi vince Barbara.
La strategia vincente consiste nel lasciare sul tavolo $1535$ che sarebbe $2^9\cdot 3-1$. Poi qualsiasi mossa fa Alberto, al turno dopo Barbara gli lascerà $2^8\cdot 3-1$ cerini e così via.. alla fine Barbara le gli lascia $2$ cerini, Alberto ne toglie 1 e vince Barbara.
"xXStephXx":
Quindi Alberto vince con tutti e soli i numeri del tipo $2,5,11,23,47...$ e così via. E la formula che genera questi numeri è [tex]3\cdot 2^k-1[/tex].
non ho capito qui...
In pratica nelle partite che cominciano con un numero di cerini uguale a $2$, $5$, $11$, ... e così via dovrebbe vincere Alberto. Ma in realtà potrebbe essere tutto il contrario Dipende quanto ci ho capito sul fatto che chi lascia 1 cerino perde.
Dipende quanto ci ho capito sul fatto che chi lascia 1 cerino perde.
La soluzione di xXStephXx è corretta. Mettiti nei panni di Barbara che comincia. Se avesse 2 cerini avrebbe perso in ogni caso, con 3 o 4 invece ne potrebbe lasciare 2 ad Alberto e far perdere lui. Con 5 avrebbe perso. Allo stesso modo se ne avesse 11, Alberto riuscirebbe a lasciargliene 5. Raddoppiando ed aumentando di uno quindi si ottiene sempre un numero di cerini con cui Barbara perderebbe sicuramente. 2 - 5 - 11 - 23 - 47 - 95 - 191 - 383 - 767 - 1535.
Siccome Barbara inizia con 1999 cerini, ne toglie all'inizio 464. E fa in modo sempre di lasciargliene ad Alberto 767, poi 383, ecc ecc, finché il povero Alberto non rimane con 2 cerini sul tavolo, ed è costretto quindi a lasciarne 1.
Siccome Barbara inizia con 1999 cerini, ne toglie all'inizio 464. E fa in modo sempre di lasciargliene ad Alberto 767, poi 383, ecc ecc, finché il povero Alberto non rimane con 2 cerini sul tavolo, ed è costretto quindi a lasciarne 1.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo