 |
Az A. 691. feladat (2017. február) |
A. 691. Legyen \(\displaystyle c\ge3\) egész szám, és definiáljuk az \(\displaystyle a_1,a_2,\dots\) sorozatot a következő rekurzióval:
\(\displaystyle a_1=c^2-1, \quad a_{n+1}=a_n^3-3a_n^2+3 \quad (n=1,2,\ldots). \)
Mutassuk meg, hogy bármely \(\displaystyle n\ge2\) egészre az \(\displaystyle a_n\) számnak van olyan prímosztója, amely nem osztja \(\displaystyle a_1,\ldots,a_{n-1}\) egyikét sem.
(5 pont)
A beküldési határidő 2017. március 10-én LEJÁRT.
Megoldás. Először a sorozat következő tulajdonságait bizonyítjuk:
(1) \(\displaystyle a_n\ge4\) minden pozitív egész \(\displaystyle n\)-re;
(2) \(\displaystyle a_n\) nem osztható \(\displaystyle 9\)-cel, ha \(\displaystyle n\ge 2\);
(3) \(\displaystyle a_n\equiv 3\pmod{a_k}\) bármilyen \(\displaystyle n>k\) pozitív egész pár esetén.
Az (1) bizonyítása triviális \(\displaystyle n\) szerinti indukcióval: \(\displaystyle n=1\)-re \(\displaystyle a_n=a_1=c^2-1\ge 3^2-1>4\). Ha pedig valamely \(\displaystyle n\)-re \(\displaystyle a_n\ge4\), akkor
\(\displaystyle a_{n+1} = a_n^3-3a_n^2+3 = a_n^2(a_n-3)+3 > 1+3 = 4. \)
A (2) bizonyításához írjuk fel a rekurzót \(\displaystyle (n-1)\)-re:
\(\displaystyle a_n = a_{n-1}^2(a_{n-1}-3)+3. \)
Ha \(\displaystyle a_{n-1}\) nem osztható \(\displaystyle 3\)-nal, akkor az \(\displaystyle a_{n-1}^2(a_{n-1}-3)\) szorzat sem osztható \(\displaystyle 3\)-mal, így \(\displaystyle a_n\) sem osztható sem \(\displaystyle 3\)-mal, sem \(\displaystyle 9\)-cel. Ha pedig \(\displaystyle a_{n-1}\) osztható \(\displaystyle 3\)-nal, akkor az első tag, \(\displaystyle a_{n-1}^2(a_{n-1}-3)\) osztható \(\displaystyle 9\)-cel, így \(\displaystyle a_n\equiv3\pmod{9}\).
A (3) állítást is \(\displaystyle n\) szerinti indukcióval igazoljuk. A legkisebb \(\displaystyle n\), ami szóba jöhet, az \(\displaystyle n=k+1\); erre
\(\displaystyle a_{k+1} = a_k^3-3a_k^2+3 \equiv 3 \pmod{a_k}. \)
Ha (3) igaz valamely \(\displaystyle n>k\)-re, azaz \(\displaystyle a_n\equiv 3\pmod{a_k}\), akkor a következő, \(\displaystyle n+1\) értékre is igaz:
\(\displaystyle a_{n+1} = a_n^3-3a_n^2+3 \equiv 3^3-3\cdot 3^2+3 = 3 \pmod{a_k}. \)
Ezután rátérhetünk a feladat megoldására. Tekintsünk egy tetszőleges \(\displaystyle n\ge2\) indexet; azt kell igazolnunk, hogy \(\displaystyle a_n\)-nek van olyan prímosztója, ami nem osztja \(\displaystyle a_1,\ldots,a_{n-1}\) egyikét sem.
Az (1) szerint \(\displaystyle a_n>3\), a (2) szerint \(\displaystyle a_n\) nem osztható \(\displaystyle 9\)-cel, ezért az \(\displaystyle a_n\)-nek biztosan van egy \(\displaystyle 3\)-től különböző prímosztója; legyen \(\displaystyle p\) egy ilyen prím.
A (3) állítás szerint bármely \(\displaystyle k<n\) esetén \(\displaystyle a_n-Ka_k=3\) valamilyen \(\displaystyle K\) egész számmal. Ha \(\displaystyle p\) közös osztója lenne \(\displaystyle a_n\)-nek és \(\displaystyle a_k\)-nak, akkor \(\displaystyle a_n-Ka_k=3\) is osztható lenne \(\displaystyle p\)-vel, márpedig \(\displaystyle p\ne3\). Így \(\displaystyle p\) nem lehet osztója \(\displaystyle a_k\)-nak semmilyen \(\displaystyle k<n\) esetén sem.
Statisztika:
17 dolgozat érkezett. 5 pontot kapott: Baran Zsuzsanna, Bukva Balázs, Gáspár Attila, Imolay András, Keresztes László, Kővári Péter Viktor, Matolcsi Dávid, Németh 123 Balázs, Schrettner Jakab, Williams Kada. 4 pontot kapott: Borbényi Márton, Kerekes Anna, Keresztfalvi Bálint, Lajkó Kálmán, Tóth Viktor, Váli Benedek. 3 pontot kapott: 1 versenyző.
A KöMaL 2017. februári matematika feladatai