GAMElandia

[scambret]

Alberto contro il PC
Il gioco è semplice
1. Il PC sceglie un numero naturale $k$
2. Partendo dal numero $4$, Alberto in un numero finito di mosse deve raggiungere il numero $k$ con le seguenti tre mosse

A. Moltiplicare il numero che si ha per 10
B. Moltiplicare il numero che si ha per 10 e sommare 4
C. Dividere il numero che si ha (a patto che è pari) per 2

Il PC vince se Alberto non riesce ad arrivare a $k$.
Quali valori di $k$ sceglierà il Pc?

[xXStephXx]

Il pc può scegliere anche $0$ vero? Fossi in te lo hackererei per impedirglielo!

[maurizio43]

Mi sembra che anche 3 possa dare dei problemi al povero Alberto .

[xXStephXx]

Il $3$ lo ottiene con:
$4 \rightarrow 2 \rightarrow 24 \rightarrow 12 \rightarrow 6 \rightarrow 3$

Non cercare troppi controesempi!

[Gottinger95]

Soluzione:

Testo nascosto:

Consideriamo il problema inverso: cercare di raggiungere 4 partendo da \(k\), con le mosse inverse:
1. \(k \rightarrow 2k\);
2. \(k \rightarrow k/10\);
3. \(k \rightarrow (k-4)/10\);
Per semplicità vogliamo raggiungere 1 (tanto basta usare 2 volte la 1). Dimostreremo che con una certa sequenza di mosse si riesce sempre ad arrivare a un numero più piccolo; questo implica che a un certo punto si raggiunge 1.
Consideriamo \(r \equiv k \pmod{10}\), \(0 \leq r \leq 9\): si nota che, per \(r \neq 9 \pmod{10}\), mi bastano al massimo 3 moltiplicazioni per 2 per arrivare a un numero congruo a 4 o a 0 mod 10, dove posso applicare la 3. A questo punto, detto \(f(k)=2^mk\) tale che \(f(k) \equiv 4 \pmod{10}\), abbiamo
\(f(k) < \frac{8k-4}{10} < \frac{4}{5}k < k\) WIN
Per \(r \equiv 9\), ci basta applicare il processo 3 volte:
1) Quattro moltiplicazioni per 2; si arriva a un numero congruo a 3 mod 10;
2) Tre moltiplicazioni per 2; si arriva a un numero congruo a 2 mod 10;
3) Una moltiplicazione per 2; si arriva a un numero congruo a 4 mod 10.
Perciò:
\(f^3(k) < \frac{2}{10}\frac{8}{10}\frac{16}{10}k = \frac{32}{125}k < k\) WIN

[xXStephXx]

Non riesco a capire il caso $r$ congruo a $9$. In che senso con $4$ moltiplicazioni per $2$ arrivo ad un numero congruo a $3$ modulo $10$?