Imo 1 - 2017 (il piú facile...)

[nuoveolimpiadi1999]

Per ogni intero $a_0 > 1$, si definisce la successione $a_0, a_1, a_2, \ldots$ tale che per ogni $n \geq 0$:
$$a_{n+1} =
\begin{cases}
\sqrt{a_n} & \text{se } \sqrt{a_n} \text{ è un intero,} \\
a_n + 3 & \text{altrimenti.}
\end{cases}
$$
Determinare tutti i valori di $a_0$ per cui esiste un numero $A$ tale che $a_n = A$ per infiniti valori di $n$.

[Talete]

Solo oggi inizio a guardare i problemi delle IMO (causa scarso tempo nelle ultime settimane). Questo mi è parso abbastanza facile, sempre che io abbia azzeccato il claim.

Claim: esiste un dato $A$ se e solo se $3\mid a_0$.

Lemma banale. Se esiste un $n$ per cui $a_n$ è multiplo di $3$, allora $a_n$ è multiplo di $3$ per ogni $n$. (È un porismo!! Ivan Izmestiev confirmed! @MATHia)

Caso in cui $a_0\equiv2\pmod{3}$. Dimostriamo per induzione che $a_{n+1}=a_n+3$ per ogni $n$. Se così non fosse, allora sia $n_0$ il minimo intero per cui $a_{n_0+1}=\sqrt{a_{n_0}}$, e quindi $a_{n_0}$ è un quadrato perfetto. Ma siccome $a_{n+1}=a_n+3$ per ogni $n<n_0$, allora $a_n=a_0+3n$ per ogni $n\le n_0$, quindi in particolare anche per $n=n_0$. Ma dunque $a_{n_0}\equiv a_0+3n_0\equiv a_0\equiv2\pmod{3}$, e non può essere un quadrato perfetto, assurdo.

Caso in cui $a_0\equiv1\pmod{3}$. Dimostriamo per induzione estesa che per ogni scelta di $a_0$ si ha, per un qualche $n$, $a_n\equiv2\pmod{3}$. Questo implicherebbe la tesi per quanto detto prima. Chiaramente per $a_0=4$ funziona ($a_1=2\equiv2\pmod{3}$). Sia ora fissato $a_0\equiv1\pmod{3}$ e sia $m:=\left\lfloor\sqrt{a_0}\right\rfloor$, in modo che
\[m^2\le a_0<(m+1)^2.\]
Se $a_0=m^2$, allora $a_1=m$. Definisco $a_k:=a_1=m$ in questo caso. Se invece $a_0>m^2$, allora prima o poi esisterà un $n$ tale che $a_n=(m+1)^2$ oppure $a_n=(m+2)^2$. Infatti, si ha che $(m+1)^2\equiv1\pmod{3}$ oppure $(m+1)^2\equiv0\pmod{3}$, e in questo secondo caso $(m+2)^2\equiv1\pmod{3}$. E dunque $a_{n+1}=m+1$ oppure $a_{n+1}=m+2$ in questi casi. Definisco $a_k:=a_{n+1}$ in questi casi.

Ho adesso un $a_k$ minore di $a_0$ e non multiplo di $3$ (se fosse multiplo di $3$, lo sarebbe anche $a_0$ per il Lemma). Se $a_k\equiv2\pmod{3}$, ho la mia tesi. Se $a_k\equiv1\pmod{3}$, per forza deve essere $a_k>1$ e quindi abbiamo dimostrato la tesi per ipotesi induttiva estesa. L'unica cosa che manca è mostrare che $a_k<a_0$, ma è vero perché
\[a_k\le m+2<m^2\le a_0,\]
che è vera perché $m\ge2$.

Caso in cui $a_0\equiv0\pmod{3}$. In realtà questo caso è molto simile al precedente: per $a_0=3$ si ha la successione $3,6,9,3,6,9,\ldots$ e questo mostra la tesi anche per $a_0=6$ e $a_0=9$. Per $a_0$ più grandi, sia $m:=\left\lfloor\sqrt{a_0}\right\rfloor$, in modo che
\[m^2\le a_0<(m+1)^2,\]
e quindi prima o poi esiste un $k$ tale che $a_k\in\{m,m+1,m+2\}$. Ma anche $a_k$ è multiplo di $3$ per il Lemma, e quindi vale l'ipotesi induttiva estesa perché $a_k<a_0$ (dato che abbiamo supposto $a_0>9$).

Sono stato molto sbrigativo, spero sia giusta!

[nuoveolimpiadi1999]

Grande Talete!
La tua soluzione ancora non l'ho letta per bene, ma mi sembra buona.

[Talete]

Grande Talete!
La tua soluzione ancora non l'ho letta per bene, ma mi sembra buona.

Oh be', spero sia buona, però dai una volta azzeccato il claim era in discesa