A B. 4272. feladat (2010. május)

B. 4272. Az (a_n) sorozat elemei pozitív egész számok és minden n $\ge$ 1 esetén a_n+1=a_n²+5a_n+1 teljesül. Lehet-e a sorozat összes tagja összetett szám?

(5 pont)

A beküldési határidő 2010. június 10-én LEJÁRT.

Megoldás. Az $\displaystyle (x_n)$ sorozatot nevezzük jónak, ha $\displaystyle x_1$ nemnegatív egész szám és minden $\displaystyle n\ge 1$ esetén $\displaystyle x_{n+1}= x_n^2+ 5x_n+1$ teljesül, ekkor $\displaystyle x_n$ elemei nemnegatív egész számok szigorúan növő sorozatát alkotják. Világos, hogy ha az $\displaystyle (x_n)$ sorozat jó, akkor minden rögzített $\displaystyle k$ nemnegatív egész esetén az $\displaystyle x'_n=x_{n+k}$ képlet által definiált $\displaystyle (x'_n)$ sorozat is jó. Továbbá, ha $\displaystyle (x_n)$ és $\displaystyle (y_n)$ is jó sorozat és $\displaystyle x_n\equiv y_n\pmod{N}$ teljesül valamely $\displaystyle n,N$ pozitív egészekre, akkor $\displaystyle x_i\equiv y_i\pmod{N}$ teljesül minden $\displaystyle i\ge n$ esetén.

Tekintsük azt a $\displaystyle (b_n)$ jó sorozatot, amelyre $\displaystyle b_1=0$, ekkor $\displaystyle b_2=1$, $\displaystyle b_3=7$, $\displaystyle b_4=85=5\cdot 17$. A fenti észrevételek szerint, ha az az $\displaystyle (a_n)$ jó sorozat valamelyik eleme 7-tel osztva 0 vagy 1 maradékot ad, akkor attól kedve a sorozat elemei 7-tel osztva felváltva 0, illetve 1 maradékot adnak. Hasonlóképpen, ha a sorozat valemelyik eleme 5-tel (17-tel) osztva 0, 1 vagy 2 (0, 1 vagy 7) maradékot ad, akkor attól kezdve a sorozat elemeinek 5-tel (17-tel) való osztási maradéka olyan sorozatot eredményez, amelyben a 0, 1, 2 (0, 1, 7) számok ismétlődnek periodikusan. így például az $\displaystyle a_1$ számot úgy választva, hogy az 7-tel osztva 1 maradékot adjon, könnyen elérhetjük, hogy a sorozat páros indexű tagjai mind oszthatók legyenek 7-tel. Ha arra is ügyelünk, hogy $\displaystyle a_1$ 5-tel osztva is 1 maradékot adjon, akkor az is igaz lesz, hogy az $\displaystyle a_{3k}$ elemek mind oszthatók 5-tel, ha pedig azt is megköveteljük, hogy $\displaystyle a_1$ 17-tel osztva 7 maradékot adjon, akkor az $\displaystyle a_{3k+2}$ elemek mind oszthatók lesznek 17-tel. Ha a sorozat minden eleme nagyobb, mint 17, akkor (feltéve, hogy mindez egyszerre garantálható) elérhetjük, hogy az $\displaystyle a_{6k+1}$ elemek kivételével a sorozat minden eleme összetett szám legyen. Ezt pedig tényleg garantálhatjuk, ha $\displaystyle a_1$-et olyan pozitív egésznek választjuk, amely $\displaystyle 35\cdot 17=595$-tel osztva $\displaystyle 595-34=561$ maradékot ad.

Ilyen választás mellett persze az $\displaystyle a_{6k+1}$ elemek sem 5-tel, sem 7-tel, sem pedig 17-tel nem lesznek oszthatók. Nézzük meg azonban a fenti sorozat $\displaystyle b_7$ elemét. Ez nyilván osztható 5-tel, 7-tel és 17-tel is. Azt állítjuk, hogy ezeken felül még legalább egy további $\displaystyle p$ prímszámmal is osztható. Mivel $\displaystyle b_7>b_4=7651>595$, ehhez csak azt kell látnunk, hogy $\displaystyle b_7$ nem osztható sem $\displaystyle 5^2$-nel, sem $\displaystyle 7^2$-nel, sem pedig $\displaystyle 17^2$-nel. Mivel $\displaystyle b_5\equiv 1\equiv b_2\pmod{25}$, látható, hogy $\displaystyle b_7\equiv b_4\equiv 10\pmod{25}$, tehát $\displaystyle b_7$ valóban nem osztható 25-tel. Modulo 49 számolva $\displaystyle b_4$ 36, $\displaystyle b_5$ pedig 7 maradékot ad, ugyanúgy, mint $\displaystyle b_3$, és így $\displaystyle b_7$ is 7 maradékot kell adjon. Végül modulo 289 számolva $\displaystyle b_5\equiv 137$, $\displaystyle b_6\equiv 92$, $\displaystyle b_7\equiv 255\not\equiv 0$. Létezik tehát egy olyan $\displaystyle p\ne 5,7,17$ prímszám, amely osztja a $\displaystyle b_7$ számot. Ha tehát az $\displaystyle a_1$ szám megválasztásánál ügyelünk arra, hogy az $\displaystyle p$-vel osztható legyen, akkor a sorozat összes $\displaystyle a_{6k+1}$ alakú eleme osztható lesz $\displaystyle p$-vel.

Összefoglalva, ha az $\displaystyle a_1>p$ szám a $\displaystyle p$ prímnek olyan többszöröse, amely 595-tel osztva 561 maradékot ad, akkor az $\displaystyle (a_n)$ jó sorozat valamennyi eleme összetett szám lesz. Minthogy azonban $\displaystyle p$ relatív prím az 595-höz, a $\displaystyle 2p, 3p,\ldots, 596p$ számok 595-tel osztva mind különböző maradékot adnak, melyek között elő kell forduljon az 561 is. Létezik tehát olyan jó sorozat, amelynek minden tagja összetett szám.

Statisztika:

17 dolgozat érkezett.

5 pontot kapott: Damásdi Gábor, Éles András, Janzer Olivér, Karkus Zsuzsa, Medek Ákos, Mester Márton, Mészáros András, Nagy Róbert, Perjési Gábor, Somogyi Ákos, Weisz Ágoston, Weisz Gellért.

4 pontot kapott: Dudás 002 Zsolt, Gyarmati Máté, Szabó 928 Attila, Tossenberger Tamás.

0 pontot kapott: 1 versenyző.

A KöMaL 2010. májusi matematika feladatai

17 dolgozat érkezett.
5 pontot kapott:	Damásdi Gábor, Éles András, Janzer Olivér, Karkus Zsuzsa, Medek Ákos, Mester Márton, Mészáros András, Nagy Róbert, Perjési Gábor, Somogyi Ákos, Weisz Ágoston, Weisz Gellért.
4 pontot kapott:	Dudás 002 Zsolt, Gyarmati Máté, Szabó 928 Attila, Tossenberger Tamás.
0 pontot kapott:	1 versenyző.

Már regisztráltál?
Új vendég vagy?