OliForum Matematico

Sulla lavagna c'è scritto un numero. A turno due giocatori cancellano il numero che trovano scritto sulla lavagna (supponiamo $n$) e lo sostituiscono con un numero ottenuto sottraendo ad $n$ un intero positivo minore o uguale della somma delle cifre di $n$. Vince il giocatore che riesce a scrivere $0$.

i) Chi vince se il numero iniziale è $766676$ ?
ii) Chi vince se il numero iniziale è $6766676667690$ ?

Sulla parte ii) mi sono davvero bloccato. Per la parte i), invece:

Sia \(s(n)\) la somma delle cifre di \(n\), e sia \((a_n)\) una serie definita così:
\(a_0=0,\)
\(\displaystyle
a_n=
\begin{cases}
1, &\mbox{ se } \exists \ \ k,\ \ n-s(n) \le k < n\ \ :\ \ a_k=0 \\
0, & \mbox{ altrimenti}
\end{cases}
\)

Evidentemente se \(a_n=0\) iniziando da \(n\) si perde, mentre se \(a_n=1\) iniziando da \(n\) si vince.
Dimostriamo che se \(n \not \equiv 0 \pmod{10}\), allora \(a_n=1\). Sia \(n=10q+r\) la divisione euclidea di \(n\) rispetto a 10.

Notiamo che vale \(10q-s(10q)=n-s(n)\), da cui:
1. Se \(a_{10q} = 0\), allora \(a_n=1\), perchè \(n-s(n) = 10q-s(10q) \le 10q < n\);
2. Se \(a_{10q}=1\), allora esiste un \(k\) tale che \( 10q-s(10q) \le k < 10q \) tale che \(a_k=0\); ma allora
\(n-s(n) = 10q-s(10q) \le k < 10q < n\), da cui segue \(a_n=1\).

Hintarello per il 2?

Ok è giusto
Nella seconda parte non è proprio un caso se compare uno $0$ scomodo alla fine xD
Ed è anche difficile dare hint che non portino vicino alla soluzione in effetti..

Volendo

hint lieve: hint medio: hintone vero (che però è meglio non guardare se prima non si ha provato)

Dai, I can do it!
1. Se \(n \not \equiv 0 \pmod{10}\), \(a_n=1\), e l'abbiamo già dimostrato prima.
2. Se \(n \equiv 0 \pmod{10}\), visto che per definizione ci interessano solo gli \(a_k=0\) per determinare i successivi \(a_m\), facciamo questo giochino: dividiamo tutti i numeri multipli di 10 per 10 dimenticandoci degli altri, e introducendo questa nuova regoletta:
\(\displaystyle
a_n=
\begin{cases}
1, &\mbox{ se } \exists \ \ k,\ \ n-\left \lfloor \frac{s(n)}{10} \right \rfloor \le k < n\ \ :\ \ a_k=0 \\
0, & \mbox{ altrimenti}
\end{cases}
\)
3. Fatto che abbiamo già usato prima: se \(n-\left \lfloor \frac{s(n)}{10} \right \rfloor = m-\left \lfloor \frac{s(m)}{10} \right \rfloor\) e \(n >m\), allora \(a_n=1\): in pratica se raggiungo gli stessi numeri di qualcuno più piccolo di me vinco sempre. In particolare notiamo che se \(s(n) \equiv 0 \pmod{10}\), allora \(a_n=1\), infatti:
\( n- \left \lfloor \frac{s(n)}{10} \right \rfloor = n-1 - \left ( \left \lfloor \frac{s(n)}{10} \right \rfloor -1 \right ) = n-1 - \left (\left \lfloor \frac{s(n-1)}{10} \right \rfloor \right ) \)
perchè \(s(n-1)\) "slitta" al multiplo di 10 precedente.

4. Nuovo fatto: se \(a (n-\left \lfloor \frac{s(n)}{10} \right \rfloor-1)\) vale 1 (regà con il pedice è illeggibile) e \(s(n) \not \equiv 0 \pmod{10}\), allora \(a_n=1\).
Innanzitutto se \(s(n) \not \equiv 0 \pmod{10}\), allora \( \left \lfloor \frac{s(n)}{10} \right \rfloor = \left \lfloor \frac{s(n-1)}{10} \right \rfloor\).
Dunque, se per assurdo \(a_n=0\), allora tutti gli \(a_k\) con \(n-\left \lfloor \frac{s(n)}{10} \right \rfloor \le k < n\) dovrebbero essere 1. Ma allora il cacchio di 0 dove l'avrà preso \(a_{n-1}\)? Visto che \(n-1-\left \lfloor \frac{s(n-1)}{10} \right \rfloor = n-\left \lfloor \frac{s(n)}{10} \right \rfloor - 1\), l'unico candidato è \(a(n-\left \lfloor \frac{s(n)}{10} \right \rfloor-1)\), che però per ipotesi è 1. Assurdo.

Armati di questi due nuovi fatti, torniamo al numero \(k\) della parte ii) (considerato senza 0 finale, secondo la semplificazione di prima).
Ha \(s(k) = 78\), e - toh guarda - abbiamo che \( s(k-\left \lfloor \frac{s(k}{10} \right \rfloor-1) = s(k-8) = 70 \equiv 0 \pmod{10}\).
Per il primo fatto, \(a_{k-8} = 1\); per il secondo fatto, \(a_k = 1\), che conclude il problema.

Gottinger95 ha scritto: Ma allora il cacchio di 0 dove l'avrà preso \(a_{n-1}\)?

Dopo tutta quella notazione, questa è stata la parte più convincente!

Ok sì quadra tutto xDD
Il problema originale chiedeva direttamente chi vince con $1234567890$ (ma non causa troppo perdimento ), però era come il secondo caso. Quindi immagino che trovare un criterio generale che permette di stabilire il vincitore dato $n$ sia troppo difficile xD Ma eventualmente c'è un modo?

xXStephXx ha scritto:

Gottinger95 ha scritto: Ma allora il cacchio di 0 dove l'avrà preso \(a_{n-1}\)?

Dopo tutta quella notazione, questa è stata la parte più convincente!

Ahahahah xD Comunque ohibò, cercare un criterio generale era quello che mi aveva bloccato: non sono riuscito a trovare qualcosa di generale, se non altri casi e casucci applicando il fatto 2 ripetutamente. Il fattaccio è che si possono determinare bene alcuni 1, ma gli 0 sono ben più difficili da trovare. Già trovare degli \(a_n = 0\) secondo me sarebbe un passo avanti Orsù, mettiamoci sotto e massacriamo questo maledetto gioco