KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

MBUTTONS

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

B. 4471. Find those polynomial functions of integer coefficients that assign a positive prime number to every Fibonacci number. (The sequence Fn of Fibonacci numbers is defined by the recurrence relation Fn=Fn-1+Fn-2 with seed values F0=0, F1=1.)

(6 points)

Deadline expired on 10 October 2012.


Google Translation (Sorry, the solution is published in Hungarian only.)

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.


Statistics on problem B. 4471.
44 students sent a solution.
6 points:Á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 points:Dinev Georgi, Homonnay Bálint, Seress Dániel, Tardos Jakab, Venczel Tünde.
4 points:5 students.
1 point:1 student.
0 point:5 students.


  • Problems in Mathematics of KöMaL, September 2012

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley