OliForum Matematico

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