Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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