Feladat:	2017. évi Nemzetközi Matematika Diákolimpia 11. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Gáspár Attila
Füzet:	2017/október, 386 - 387. oldal		PDF  |  MathML
Témakör(ök):	Nemzetközi Matematikai Diákolimpia, Rekurzív sorozatok, Teljes indukció módszere, Esetvizsgálat
Hivatkozás(ok):	Feladatok: 2017/szeptember: 2017. évi Nemzetközi Matematika Diákolimpia 11. 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.   Gáspár Attila megoldása.   1. állítás: Ha $a_0\equiv 0\left(\text{mod}3\right)$, akkor a sorozat tartalmazza a $3$-at.   Bizonyítsunk $a_0$ szerinti teljes indukcióval. Ha $a_0=3$, akkor az állítás triviális. Ha $a_0=6$, akkor $a_1=9$, és $a_2=3$, ezért az állítás igaz. A továbbiakban feltételezhetjük, hogy $a_0\ge 9$. Látható, hogy az $a_0\mathrm{,}{a}_0+\mathrm{3,}{a}_0+\mathrm{6,}\text{...}$ számtani sorozatban van az első négyzetszám a sorozatból. A sorozat összes eleme 3-mal osztható, ezért ez a négyzetszám $x^2={\left(3k\right)}^2$ alakú. Végtelen sok 3-mal osztható négyzetszám van, ezért a sorozat tartalmaz négyzetszámot. A ${\left(3\left(k-1\right)\right)}^2={\left(x-3\right)}^2$ nem szerepel a sorozatban, ezért $a_0>{\left(x-3\right)}^2=x^2-6x+9=x\left(x-6\right)+9>x+9>x$. Az $x^2$ szerepel a sorozatban, ezért az $x$ is szerepel. $x<a_0$, ezért az indukciós feltevés miatt az állítás igaz. Látható, hogy ha $a_0=3$, akkor $a_1=6$, $a_2=9$ és $a_3=3$. Ha $3\mid a_0$, akkor az 1. állítás miatt a 3 végtelen sokszor szerepel a sorozatban.   2. állítás: Ha $a_0\equiv 1\left(\text{mod}3\right)$, akkor a sorozat tartalmaz $3k+2$ alakú számot.   Bizonyítsunk $a_0$ szerinti teljes indukcióval. Ha $a_0=1$, akkor $a_1=4$, és $a_2=2$. Ebből látható, hogy az állítás $a_0=4$ esetén is igaz. A továbbiakban feltételezhetjük, hogy $a_0\ge 7$. Látható, hogy az $a_0\mathrm{,}{a}_0+\mathrm{3,}{a}_0+\mathrm{6,}\text{...}$ számtani sorozatban van az első négyzetszám a sorozatból. Ilyen biztosan van, mert végtelen sok $3k+1$ alakú négyzetszám van. Legyen ez a négyzetszám $x^2$. Az $x^2$ szerepel a sorozatban, ezért az $x$ is szerepel. Ha $x=3k+2$ alakú, akkor az állítás igaz. Ha $x=3k+1$ alakú, akkor a ${\left(3k-1\right)}^2={\left(x-2\right)}^2$ nem szerepel a sorozatban, ezért $a_0>{\left(x-2\right)}^2=x^2-4x+4=x\left(x-4\right)+4>x+4>x$. Az indukciós feltevés miatt az állítás igaz.   3. állítás: Ha $a_0\equiv 2\left(\text{mod}3\right)$, akkor a sorozat szigorúan monoton növekvő.   Egy négyzetszám nem lehet $3k+2$ alakú. Így az $a_0\mathrm{,}{a}_0+\mathrm{3,}{a}_0+\mathrm{6,}\text{...}$ sorozat nem tartalmaz négyzetszámot. Ekkor $a_1=a_0+3$, $a_2=a_0+6$, $\text{...}$, $a_n=a_0+3n$. Ezzel az állítást igazoltuk. Látható, hogy ha $a_0$ nem osztható 3-mal, akkor a 2. és 3. állítás miatt a sorozat egy idő után szigorúan monoton növekvő. Így nincs olyan $A$, amit végtelen sokszor tartalmaz. Tehát pontosan akkor van olyan $A$, amit végtelen sokszor tartalmaz a sorozat, ha $3\mid a_0$.