OliForum Matematico

(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$.

Sbaglio o, così ad occhio, Alberto ha una strategia vincente ogni volta che $2n \le m$?

Sbagli comunque ad occhio sembra così, è vero...

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?

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

Scusa, non so leggere... Avevo capito che si dovesse trovare $a$ tale che Alberto avesse una strategia vincente sse (quella roba). Ok, ora dovrebbe essere tutto chiaro.

Tranquillo, nessun problema Però continua, la strada è buona!

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

Ok, tutto giusto