|
Feladat: |
N.115 |
Korcsoport: 18- |
Nehézségi fok: nehéz |
Megoldó(k): |
Bérczi Gergely , Braun Gábor , Czimmermann Péter , Frenkel Péter , Gyenes Zoltán , Juhász András , Kun Gábor , Kutalik Zoltán , Lippner Gábor , Lukács László , Mátrai Tamás , Pap Gyula , Prause István , Szabó Jácint , Terék Zsolt , Terpai Tamás |
Füzet: |
1997/szeptember,
353 - 354. oldal |
PDF | MathML |
Témakör(ök): |
Szakaszos tizedestörtek, Teljes indukció módszere, Számsorozatok, Nehéz feladat |
Hivatkozás(ok): | Feladatok: 1996/október: N.115 |
|
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. Teljes indukcióval könnyen igazolható, hogy tetszőleges, a lépések során keletkező számhármasra . Ennek következménye, hogy , valamint hogy a lépések során keletkező törtek sohasem egyszerűsíthetők. A számhármasok rendezettsége megadja azt az algoritmust is, amellyel a kívánt középső elemet kell elérnünk. Ha az számhármasból kell tovább lépnünk, akkor három eset lehetséges:
* | 1. Ha , akkor a számot kell letörölnünk és az , számokkal kell tovább dolgoznunk, mert ebben az esetben az összes további mediáns az intervallumban lesz; |
* | 2. Ha , akkor az számot kell letörölnünk, és a , számokkal kell folytatnunk a műveletet; |
* | 3. Ha , akkor találtunk egy olyan számhármast, amelynek középső eleme . Tovább folytatni nem szabad, mert az előbbi okok miatt semelyik újabb mediáns nem lehet . | A fentiek alapján a számot nem lehet két különböző módon előállítani. Azt kell még igazolnunk, hogy az eljárás biztosan előállítja -t, azaz véges sok lépésben véget ér. Legyen , az -edik lépésben keletkező számhármas . Megmutatjuk, hogy a sorozat szigorúan monoton fogy. Ebből a végesség következik, mert a sorozat pozitív egészekből áll.
Legyen az -edik számhármas , amelyben és . Ekkor esetén | | a esetben pedig | |
Megjegyzések. 1. A megoldás kis módosításával az is igazolható, hogy ha nem a , hanem tetszőleges számhármasból indulunk ki, akkor is tetszőleges racionális szám egyértelműen állítható elő.
Braun Gábor (Budapest, Szent István Gimn., IV. o.) |
2. Az, hogy az eljárás előállítja -t, bebizonyítható a lépések egyszerű megfordításával is. Ha és ez a tört nem egyszerűsíthető, akkor egyértelműen léteznek olyan nemnegatív egész számok, amelyekre , ezekkel a számokkal az utolsó számhármas csak lehet. Nem nehéz bebizonyítani, hogy egy ilyen számhármasból mindig lehet visszafelé lépni, kivéve a számhármast. A visszafelé lépegetés közben a törtek nevezői csökkennek, ezért az eljárás csakugyan megadja előállítását. 3. Ha nagyság szerint sorbarendezzük azokat a -beli, nem egyszerűsíthető törteket, amelyek nevezője legfeljebb , akkor az úgynevezett -edik Farey-sorozatot kapjuk. Például az -ödik Farey-sorozat: | | Ebben a sorozatban bármely két szomszédos , elemre , továbbá, ha valamelyik tört nevezője nagyobb, mint a két szomszédjáé, akkor a tört a két szomszédjának a mediánsa. (A Farey-sorozatokról bővebben lásd pl. Niven‐Zuckermann: Bevezetés a számelméletbe, 6. fejezet) |
|