Kezdőlap


Feladat:	N.164	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Baharev Ali , Bérczi Gergely , Csóka Endre , Gerbicz Róbert , Gyenes Zoltán , Győri Nikolett , Hegedűs Péter , Horváth Gábor , Juhász András , Kun Gábor , Lippner Gábor , Lukács László , Mecz Balázs , Naszódi Gergely , Pataki Péter , Székelyhidi Gábor , Végh A. László , Zábrádi Gergely
Füzet:	1998/október, 422 - 423. oldal		PDF \| MathML
Témakör(ök):	Fibonacci-sorozat, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1998/február: N.164

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.

Jelölje $f_{i}$ a Fibonacci-sorozat $i$ -edik elemét, azaz $f_{0} = f_{1} = 1$ , $f_{n + 2} = f_{n + 1} + f_{n}$ .
A Fibonacci-sorozat értelemszerűen kiterjeszthető negatív indexekre is ( $f_{- 1} = 0$ , $f_{- 2} = 1$ , $f_{- 3} = - 1$ stb).
Bebizonyítjuk a következőt: $(f_{n})$ $m$ szerint vett maradékai periodikusak (minden $m > 1$ -re).
Tekintsük ugyanis az $(f_{i}, f_{i + 1})$ ( $i \in Z$ ) rendezett párokat modulo $m$ . Közülük véges sok, legfeljebb $m^{2}$ különböző lehetséges, így létezik olyan $i < j$ , amelyre $f_{i} \equiv f_{j}$ és $f_{i + 1} \equiv f_{j + 1}$ (mod $m$ ). Innen nyilván $f_{i - 1} \equiv f_{j - 1}$ és $f_{i + 2} \equiv f_{j + 2}$ adódik a rekurzióból, ezért teljes indukcióval azt kapjuk, hogy $(f_{n})$ az $m$ szerint vett maradékra nézve periodikus (mindkét irányban!) a $j - i$ periódussal.
Ekkor végtelen sok pozitív $j$ van, amelyre $- 1 = f_{- 3} \equiv f_{j}$ (mod $1 000 000$ ), és $j > 0$ esetén $f_{j} > 0$ ; vagyis $f_{j}$ a 10-es számrendszerben felírva 6 darab 9-esre végződik.