Un altro gioco

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Un altro gioco

Messaggio da Triarii » 22 mar 2014, 14:51

Un numero naturale è scritto su una lavagna. Due giocatori $A$ e $B$ a turni possono fare una delle seguenti mosse (una per turno)
1) Rimpiazzare il numero $n$ scritto sulla lavagna con $n-1$
2) Rimpiazzare $n$ con $\displaystyle \lfloor (n+1)/2 \rfloor$
Vince il giocatore che per primo scrive $1$. Il primo a giocare è $A$.
Se il numero iniziale è $1000000$, chi dei due giocatori vince con le mosse giuste?
"We' Inge!"
LTE4LYF

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: Un altro gioco

Messaggio da xXStephXx » 22 mar 2014, 17:39

Penso che con tutti i pari vinca il primo. Perchè ad esempio se per un certo $k$ con $2k$ vince il secondo, vuol dire che con $2k-1$ e $k$ vinceva il primo.
In particolare se con $2k-1$ vince il primo, con uno tra $2k-2$ e $k$ vince il secondo, ma con $k$ vince il primo, quindi con $2k-2$ vince il secondo. Questo vuol dire che il secondo vince con tutti i pari minori di $2k$ ma già dai primi casi si nota che non accade.
Mentre con $68719476735$ chi vince? :mrgreen:

Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: Un altro gioco

Messaggio da Triarii » 22 mar 2014, 18:39

Sì la risposta è corretta :) Appena ho un po' di tempo scrivo la mia soluzione.
Per rispondere alla tua domanda
Testo nascosto:
Visto che il tuo numero è $\equiv 3 \pmod 4$, sia che sottragga uno, oppure che aggiunga uno e poi divida ottengo in ogni caso un pari, che è una posizione che fa vincere chi parte da lì (in questo caso il secondo giocatore. Pertanto con quel numero lì il primo perde.
"We' Inge!"
LTE4LYF

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: Un altro gioco

Messaggio da xXStephXx » 22 mar 2014, 22:57

Mannaggia! Non l'avevo mica capito che si poteva raggirare così bene! :lol:
Io ero andato a pescare $2^{36}-1$ per sfruttare il fatto che se il secondo vince con $k$ vince anche con $2k+1$ xDD

Rispondi