|
Feladat: |
N.67 |
Korcsoport: 18- |
Nehézségi fok: nehéz |
Megoldó(k): |
Braun Gábor , Burcsi Péter , Farkas Péter , Gyarmati Katalin , Izsák Ferenc , Makai Márton , Pap Gyula , Póczos Barnabás , Szádeczky-Kardoss Szabolcs , Tóth Gábor Zsolt , Valkó Benedek |
Füzet: |
1996/április,
224 - 226. oldal |
PDF | MathML |
Témakör(ök): |
Oszthatóság, Konstruktív megoldási módszer, Nehéz feladat |
Hivatkozás(ok): | Feladatok: 1995/április: N.67 |
|
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. I. megoldás. Legyen , , , , , , a Fibonacci-sorozat. Azt állítjuk, hogy az alakú számpárok megfelelők lesznek. Mivel ezek a számpárok páronként különbözőek, a konstrukció végtelen sok megoldást állít elő. Bebizonyítjuk, hogy minden pozitív egészre Ebből állításunk következik, mert | | is egész szám lesz. Az (1) azonosságot teljes indukcióval igazoljuk. Az állítás igaz -re, mert . Tegyük fel, hogy (1) valamilyen -ra teljesül, és hogy esetén | | ebből következik az állítás -re: | | Az (1) azonosság tehát minden -ra teljesül.
Valkó Benedek (Fazekas M. Főv. Gyak. Gimn., IV. o. t.) |
Megjegyzés. Az (1) azonosság a Fibonacci-sorozat alábbi ismert explicit alakjából is bebizonyítható:
II. megoldás. Ha és , akkor és relatív prímek. Ha ugyanis és legnagyobb közös osztója , akkor miatt . Mivel osztható -mel és -nel is, a relatív prímség miatt osztható -nel is. Megfordítva, ha osztható -nel, akkor osztható -mel és -nel is, amiből következik, hogy és . A feltétel tehát azzal ekvivalens, hogy osztható -nel. Legyen pozitív egész, és tekintsük az egyenletet. Azt állítjuk, hogy ha ennek van pozitív egészekből álló megoldása, akkor végtelen sok is van. Ebből az állítás azonnal következik. Tegyük fel, hogy egy megoldása (2)-nek, és . Ha (2)-t egy paraméteres másodfokú egyenletnek tekintjük, amelyben az ismeretlen, akkor az egyenlet egyik gyöke , a másik pedig a gyökök és együtthatók közötti összefüggések (Vita formulák) alapján Az első formula alapján ez a gyök is egész, a második szerint pedig pozitív, sőt A (2) egyenletnek ezért az számpár egy újabb, pozitív egészekből álló megoldása, amelyben a két szám összege nagyobb, mint az előzőben: . A megoldások között tehát nincs olyan, amelyben a két ismeretlen összege maximális. Ha , akkor (2)-nek van megoldása, például . Az előbbiek szerint ebből következik, hogy végtelen sok olyan számpár van, amelyre teljesül, hogy .
Tóth Gábor Zsolt (Budapest, Árpád Gimn., III. o.t.) és |
Braun Gábor (Budapest, Szent István Gimn., II. o.t) dolgozata nyomán |
Megjegyzések. 1. A két megoldás lényegében ugyanazokat a számpárokat adja. A II. megoldásban adott konstrukció ugyanis az számpárból az számpárt állítja elő, ami megfelel az rekurziónak. Az számpárt az I. megoldás is előállítja, ha bevezetjük az , elemeket. 2. A második megoldás módszerével nem nehéz bebizonyítani, hogy más megoldás nincs. Ehhez először azt mutatjuk meg, hogy (2)-nek csak esetén van pozitív egészekből álló megoldása. Tekintsünk egy olyan megoldást, amelyben minimális. Ha , akkor és kész vagyunk. Ellenkező esetben feltehetjük, hogy (egyenlők nem lehetnek, mert relatív prímek). Definiáljuk most ismét az számot. Ez ismét pozitív egész lesz, de ezúttal | | Az számpár tehát olyan pozitív egészekből álló megoldás, amelyben . Ez viszont ellentmondás, mert feltettük, hogy minimális. Ezután már nem nehéz bebizonyítani, hogy ha egy megoldása (2)-nek, akkor és valamilyen nemnegatív egésszel. Ez ismét teljes indukcióval történhet. Ha , akkor az állítás triviális. Tegyük fel, hogy igaz esetén. Ebből bebizonyítjuk -re is. Legyen egy olyan megoldása (2)-nek, amelyben és . Mivel az is pozitív egészekből álló megoldás, de ebben és , az indukciós feltevés szerint létezik olyan nemnegatív egész szám, amelyre és . Ebből viszont következik, hogy . |
|