Gioco oscuro da oscura provenienza

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Gioco oscuro da oscura provenienza

Messaggio da Talete »

(Ce l'ha proposto l'allenatore della nostra provincia, ad uno degli incontri di preparazione a Cesenatico... ma non so da dove l'abbia preso...)

Siano $m$ ed $n$ due interi positivi con $m\ge n$. Alberto e Barbara si sfidano al seguente gioco. Sul tavolo ci sono due pile di $m$ ed $n$ gettoni e, a turno, fanno una mossa. Una mossa consiste nel togliere da una delle due pile un numero di gettoni che è un multiplo non nullo del numero di gettoni dell'altra pila. Il vincitore è il giocatore che toglie l'ultimo gettone da una delle due pile. Trovare il numero $a$ tale che Alberto non ha una strategia vincente se e solo se $a\cdot n > m\ge n$.

EDIT: modificato un segno $>$ in $\ge$.
Ultima modifica di Talete il 01 giu 2015, 19:11, modificato 3 volte in totale.
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
cip999
Messaggi: 153
Iscritto il: 26 nov 2013, 14:44

Re: Gioco oscuro da oscura provenienza

Messaggio da cip999 »

Sbaglio o, così ad occhio, Alberto ha una strategia vincente ogni volta che $2n \le m$?
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Gioco oscuro da oscura provenienza

Messaggio da Talete »

Sbagli ;) comunque ad occhio sembra così, è vero...
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
cip999
Messaggi: 153
Iscritto il: 26 nov 2013, 14:44

Re: Gioco oscuro da oscura provenienza

Messaggio da cip999 »

Mmmh... Non mi convince... Anche se probabilmente da qualche parte sto dicendo qualcosa di stupido.

Siano $A$ e $B$ le due pile, con rispettivamente $m,n$ monete, tali che $m > 2n$ (il caso $m = 2n$ è banale). Supponiamo che Alberto inizi togliendo $n$ monete dalla pila $A$. Allora abbiamo due casi:
  1. Qualunque mossa faccia Barbara, Alberto ha una strategia vincente. E qui abbiamo finito.
  2. Esiste una mossa che porta Barbara ad avere una strategia vincente. Ora, poiché il numero di monete in $A$ è ancora maggiore di quello in $B$, tale mossa consisterà nel togliere $kn$ monete da $A$. Ma allora, con la sua prima mossa Alberto avrebbe potuto togliere $(k + 1)n$ monete dalla pila $A$, così da invertire le parti e guadagnarsi una strategia vincente (quella di Barbara, appunto).
In ogni caso, Alberto vince.

Cos'è che non torna?
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Gioco oscuro da oscura provenienza

Messaggio da Talete »

L'altra freccia ;) Cioè, $2$ non è la migliore costante. Prova a fare il gioco con i numeri $4$ e $7$... Alberto dovrà per forza mandare questa configurazione in $(4,3)$ e Barbara in $(1,3)$ così Alberto vince. Ma non mi sembra che $7>4\cdot2$... l'idea è buona, comunque :)
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
cip999
Messaggi: 153
Iscritto il: 26 nov 2013, 14:44

Re: Gioco oscuro da oscura provenienza

Messaggio da cip999 »

Scusa, non so leggere... :oops: Avevo capito che si dovesse trovare $a$ tale che Alberto avesse una strategia vincente sse (quella roba). Ok, ora dovrebbe essere tutto chiaro. ;)
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Gioco oscuro da oscura provenienza

Messaggio da Talete »

Tranquillo, nessun problema ;) Però continua, la strada è buona!
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
cip999
Messaggi: 153
Iscritto il: 26 nov 2013, 14:44

Re: Gioco oscuro da oscura provenienza

Messaggio da cip999 »

Sì, ma a questo punto non è difficile concludere che $a = \phi$.

Adesso vado un po' di fretta, comunque la chiave della dimostrazione sta nel fatto che se $m > \phi n$, allora $n < \phi(m - n)$ (e viceversa).
Magari dopo la scrivo per bene. :)
cip999
Messaggi: 153
Iscritto il: 26 nov 2013, 14:44

Re: Gioco oscuro da oscura provenienza

Messaggio da cip999 »

cip999 ha scritto:Sì, ma a questo punto non è difficile concludere che $a = \phi$.

Adesso vado un po' di fretta, comunque la chiave della dimostrazione sta nel fatto che se $m > \phi n$, allora $n < \phi(m - n)$ (e viceversa).
Magari dopo la scrivo per bene. :)
Ho un po' di tempo, quindi abbozzo qualcosa.

Dunque, il caso $m \ge 2n$ è stato già trattato, quindi dimostriamo, ad esempio, che se $2n > m > \phi n$ Alberto ha una strategia vincente. Difatti, in questo caso la prima mossa di Alberto è forzata (togliere $n$ monete dalla pila da $m$). A questo punto, restano due pile da, rispettivamente, $n$ ed $m - n$ monete (con $n > m - n$). Ora, però, si ha anche $n < \phi(m - n)$, dal momento che $$\phi n < m \Rightarrow \frac{\phi + 1}{\phi}n < m \Rightarrow (\phi + 1)n < \phi m \Rightarrow n < \phi(m - n)$$ dove nel primo passaggio è stata usata la nota identità $\phi^2 = \phi + 1$.
Barbara è dunque costretta a sottrarre $m - n$ monete alla pila da $n$, e si dimostra esattamente come prima che vale $m - n > \phi(2n - m)$. Ora, se $m - n \ge 2(2n - m)$ Alberto vince; altrimenti, siamo ricaduti nella situazione iniziale, ma con meno monete. Per il principio della discesa infinita, prima o poi Barbara lascerà ad Alberto una configurazione in cui una pila ha almeno il doppio delle monete dell'altra, e quindi Alberto vince comunque.

L'altra freccia è del tutto analoga.
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Gioco oscuro da oscura provenienza

Messaggio da Talete »

Ok, tutto giusto :)
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
Rispondi