Feladat:	2018. évi Nemzetközi Matematika Diákolimpia 22. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Matolcsi Dávid
Füzet:	2018/november, 451 - 452. oldal		PDF  |  MathML
Témakör(ök):	Nemzetközi Matematikai Diákolimpia, Számsorok, Oszthatóság
Hivatkozás(ok):	Feladatok: 2018/szeptember: 2018. évi Nemzetközi Matematika Diákolimpia 22. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Matolcsi Dávid megoldása. $S\left(n\right)$-nek nevezem a feladatban definiált összeget. $N<n$-re $S\left(n\right)$ és $S\left(n+1\right)$ is egész, így $\begin{array}{c}{\displaystyle S\left(n+1\right)-S\left(n\right)=\frac{a_n}{a_{n+1}}+\frac{a_{n+1}-a_n}{a_1}}\end{array}$ is mindig egész. Legyen $\left(a_1\mathrm{,}{a}_n\right)=x$ és $a_1=x{a}_1\text{'}$, illetve $a_n=x{a}_n\text{'}$. Ekkor $\begin{array}{c}{\displaystyle a_1\text{'}\left(S\left(n+1\right)-S\left(n\right)\right)=\frac{x{a}_n\text{'}{a}_1\text{'}}{a_{n+1}}+\frac{a_{n+1}}{x}-a_n\text{'}}\end{array}$ egész szám. Tehát $\begin{array}{c}{\displaystyle \frac{x{a}_n\text{'}{a}_1\text{'}}{a_{n+1}}+\frac{a_{n+1}}{x}}\end{array}$ is egész. Legyen most $\left(a_{n+1}\mathrm{,}x\right)=y$ és $a_{n+1}=y{a}_{n+1}\text{'}$, illetve $x=yx\text{'}$. Így $\begin{array}{c}{\displaystyle \frac{x{a}_n\text{'}{a}_1\text{'}}{a_{n+1}}+\frac{a_{n+1}}{x}=\frac{a_n\text{'}{a}_1\text{'}}{a_{n+1}\text{'}}+\frac{a_{n+1}\text{'}}{x\text{'}}=\frac{x\text{'}{a}_n\text{'}{a}_1\text{'}+a_{n+1}{\text{'}}^2}{x\text{'}{a}_{n+1}\text{'}}}\end{array}$ egész. Tehát $x\text{'}\mid a_{n+1}{\text{'}}^2$. Másrészt tudjuk, hogy $\left(a_{n+1}\text{'}\mathrm{,}x\text{'}\right)=1$. Ez csak úgy lehetséges, ha $x\text{'}=1$, tehát $x=y$, azaz $x\mid a_{n+1}$. Ezzel általánosan beláttuk, hogy $\left(a_1\mathrm{,}{a}_k\right)\mid a_{k+1}$. Másrészt értelemszerűen $\left(a_1\mathrm{,}{a}_k\right)\mid a_1$, így $\left(a_1\mathrm{,}{a}_k\right)\mid \left(a_1\mathrm{,}{a}_{k+1}\right)$. Teljes indukció szerint tehát ha $k<t$, akkor $\left(a_1\mathrm{,}{a}_k\right)\mid \left(a_1\mathrm{,}{a}_t\right)$. Mivel $a_1$-nek csak véges sok osztója van, az $\left(a_1\mathrm{,}{a}_t\right)$ sorozat pedig végtelen és monoton növekvő, létezik egy $r$ korlát, amitől kezdve minden $\left(a_t\mathrm{,}{a}_1\right)=x$ egyenlő. Így ettől kezdve minden $a_t=x{a}_t\text{'}$, ahol $\left(a_t\text{'}\mathrm{,}{a}_1\text{'}\right)=1$ (ahol $a_1=x{a}_1\text{'}$). Ekkor $\begin{array}{c}{\displaystyle \frac{a_t}{a_{t+1}}+\frac{a_{t+1}-a_t}{a_1}=\frac{a_t\text{'}}{a_{t+1}\text{'}}+\frac{a_{t+1}\text{'}-a_t\text{'}}{a_1\text{'}}=\frac{a_t\text{'}{a}_1\text{'}+a_{t+1}{\text{'}}^2-a_t\text{'}{a}_{t+1}\text{'}}{a_{t+1}\text{'}{a}_1\text{'}}}\end{array}$ egész. Ez azt jelenti, hogy $a_{t+1}\text{'}\mid a_t\text{'}{a}_1\text{'}$. Mivel $\left(a_{t+1}\text{'}\mathrm{,}{a}_1\text{'}\right)=1$, ezért $a_{t+1}\text{'}\mid a_t\text{'}$. Ez az $r$ korláttól kezdve folyamatosan igaz, így $a_t\text{'}\mid a_r\text{'}$ és az $a_t\text{'}$ sorozat monoton csökkenő. Mivel $a_r\text{'}$-nek csak véges sok osztója van, a végtelen $a_t\text{'}$ sorozatnak egy $M$ korlát után minden eleme egyenlő lesz. Így $M<m$-re minden $a_m=x{a}_m\text{'}$ is egyenlő lesz, ezzel az állítást beláttuk.