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

A B. 4471. feladat (2012. szeptember)

B. 4471. Melyek azok az egész együtthatós polinomfüggvények, amelyek minden Fibonacci-számhoz pozitív prímszámot rendelnek? (A Fibonacci-számok egy rekurzív sorozat elemei: F0=0, F1=1; n>1-re pedig Fn=Fn-1+Fn-2.)

(6 pont)

A beküldési határidő 2012. október 10-én LEJÁRT.

Megoldás. Legyen f(x) egy ilyen polinomfüggvény, f(0)=f(F0)=p. Tegyük fel, hogy valamely Fn Fibonacci-szám osztható p-vel. Mivel f egész együtthatós és konstans tagja f(0), látható hogy p\mid F_n\mid f(F_n)-f(0)=f(F_n)-p. Ennélfogva p osztója az f(Fn) függvényértéknek, vagyis f(Fn)=p. Megmutatjuk, hogy végtelen sok olyan n természetes szám van, melyre p\mid F_n teljesül. Mivel a Fibonacci-számok F1=F2 kivételével mind különbözőek, ebből következik, hogy az f(x) polinomfüggvény végtelen sok helyen veszi fel a p értéket, ami azt jelenti, hogy az f(x)-p polinomfüggvénynek végtelen sok gyöke van, vagyis azonosan 0, hiszen egy k-adfokú polinomfüggvénynek legfeljebb k különböző gyöke lehet. Innen pedig már látszik, hogy a feladat megoldásai azok az f(x)=c konstans függvények, ahol c értéke pozitív prímszám, ami végtelen sok megoldást jelent.

Már csak a Fibonacci-sorozatra vonatkozó állításunkat kell igazolni. Ehhez tekintsük a sorozat elemeit modulo p. Az (Fk,Fk+1) számpárok modulo p legfeljebb p2 különböző értéket vehetnek fel, vagyis kell legyenek olyan k<m indexek, melyekre F_k\equiv F_m \pmod{p} és F_{k+1}\equiv F_{m+1} \pmod{p} is teljesül. Ekkor persze Fk+2=Fk+1+Fk és Fm+2=Fm+1+Fm miatt F_{k+2}\equiv F_{m+2} \pmod{p}. A rekurziót visszafelé alkalmazva pedig Fk-1=Fk+1-Fk és Fm-1=Fm+1-Fm alapján kapjuk, hogy F_{k-1}\equiv F_{m-1} \pmod{p} (feltéve, hogy k>0). Innen indukcióval nem nehéz belátni, hogy az m-k=n jelöléssel minden i természetes számra teljesül F_{n+i}\equiv F_i\pmod{p}, amiből adódik, hogy az F_0,F_n,F_{2n},F_{3n},\ldots Fibonacci-számok mind oszthatók p-vel.

Statisztika:

44 dolgozat érkezett.
6 pontot kapott:Ágoston Péter, Balogh Tamás, Bogár Blanka, Csernák Tamás, Fonyó Viktória, Forrás Bence, Géczi Péter Attila, Havasi 0 Márton, Ioan Laurentiu Ploscaru, Janzer Barnabás, Janzer Olivér, Kabos Eszter, Kaprinai Balázs, Kúsz Ágnes, Maga Balázs, Makk László, Nagy Róbert, Petrényi Márk, Sagmeister Ádám, Sárosdi Zsombor, Simon 047 Péter, Somogyvári Kristóf, Szabó 789 Barnabás, Szabó 928 Attila, Tossenberger Tamás, Vályi András, Varnyú József, Zilahi Tamás.
5 pontot kapott:Dinev Georgi, Homonnay Bálint, Seress Dániel, Tardos Jakab, Venczel Tünde.
4 pontot kapott:5 versenyző.
1 pontot kapott:1 versenyző.
0 pontot kapott:5 versenyző.

A KöMaL 2012. szeptemberi matematika feladatai