|
Feladat: |
B.3323 |
Korcsoport: 16-17 |
Nehézségi fok: átlagos |
Megoldó(k): |
Gáspár Merse Előd , Gerencsér Balázs , Hablicsek Márton , Kovács Erika Renáta |
Füzet: |
2000/május,
291 - 294. oldal |
PDF | MathML |
Témakör(ök): |
Racionális számok és tulajdonságaik, Oszthatóság, Diofantikus egyenletek, Fagráfok, erdők, faváz, Feladat |
Hivatkozás(ok): | Feladatok: 1999/december: B.3323 |
|
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. A feladatot megoldjuk, ha megkeressük I. azokat az és pozitív egész számokat, amelyekre , és az ilyen törtek közül a legnagyobb; illetve II. azokat a és pozitív egész számokat, amelyekre , és az ilyen törtek közül a legkisebb.
I. Vizsgáljuk a különbséget! Legyen először . Ekkor , amiből . Mivel , azért kisebb, mint 20. Így a számláló, a értéke 19 páratlan többszöröseként 19 vagy 57. A 19 nem megfelelő, mivel 18 nem osztható 4-gyel. Így , és , a tört pedig . Ebben az esetben . Ez a legkisebb különbség, mivel ha számlálója egynél nagyobb lenne, akkor a nevezőben csak 99-nél nagyobb esetén lehetne a tört kevesebb, mint . II. Vizsgáljuk most is a különbséget! Legyen először . Ekkor , amiből . Mivel , azért kisebb, mint 20. Így a számláló, értéke 19; 57 vagy 95. 57 nem megfelelő, mivel 18 nem osztható 4-gyel. 95 esetén és , túl nagy. Így , és . Ebben az esetben . Ha ennél kisebb különbséget keresünk, akkor ha számlálója , akkor legalább . Emiatt a számlálója legfeljebb 3. Ha , akkor , amiből . A fentiekhez hasonlóan ellenőrizhető, hogy csak a a megoldás, amiből és . Ha , akkor , amiből . Most csak a a megoldás, amiből és . Mindhárom eredmény az törtet adja. A feladat megoldása tehát: az a legbővebb (nyílt) intervallum, ahol a a legkisebb nevezőjű tört.
Hablicsek Márton (Fazekas M. Főv. Gyak. Gimn., 8. o.t.) |
II. megoldás. Megmutatjuk, hogy ha és , akkor az intervallumban minden tört nevezője nagyobb 99-nél ‐ valójában, mint látni fogjuk majd, -nél is. Legyen tehát . A nevezőkkel szorozva . Így (1. ábra).
1. ábra Ugyanígy igazolható, hogy ha és , akkor a intervallumban minden tört nevezője nagyobb, mint . A megoldáshoz tehát meg kell keresnünk azt a legkisebb pozitív , illetve nevezőt, amelyre | |
Ismeretes, hogy ‐ mivel , a fenti egyenleteknek van, mégpedig pontosan egy olyan , illetve megoldása, hogy és , illetve és , sőt, a egyenlőség átrendezésével kapott feltételből ezekre a minimális megoldásokra és . Az (1), (2) ún. diofantikus egyenletek megoldására több módszer ismeretes ‐ az I. megoldásban valójában ezeket az egyenleteket oldotta meg a beküldő ‐ és ezek bármelyikével , tehát , , tehát , a maximális intervallum pedig, amelyben a minimális nevezőjű tört, .
Megjegyzések. 1. A megoldásból kiderül, hogy a keresett intervallumban , a két végpont, és úgynevezett mediánja. A mediánképzés segítségével a és az törtekből kiindulva a intervallum bármely törtjéhez eljuthatunk, ezeket redukált ‐ azaz egyszerűsített ‐ alakban kapjuk, és minden tört a legbővebb olyan intervallum két végpontjának a mediánjaként áll elő, amelyben a minimális nevezőjű tört. A konstrukció leírása megtalálható Graham‐Knuth‐Patashnik: Konkrét matematika (Műszaki Könyvkiadó, 1998) c. könyve 117‐119. oldalán. A fenti könyv 118. oldalán a konstrukciót megvalósító, ún. Stern‐Brocot-fa kezdete látható (2. ábra).
2. ábra A fában az ,,'' szimbólum segítségével az 1-nél nagyobb törteket is megkapjuk. Ha úgy tetszik ‐ mint ahogyan a margón olvasható ,,graffiti'' mondja, értelmezhető a ,,végtelennek nem redukálható tört alakjában történő előállításaként''. A fában minden tört az első balra, illetve jobbra felfelé útbaejtett szám mediánja. A Stern‐Brocot-fa felhasználásával oldotta meg a feladatot Gerencsér Balázs és Kovács Erika Renáta (mindketten a Fazekas M. Főv. Gyak. Gimn., 10. osztályos tanulói). A hivatkozás után a feladat annyi, hogy a törtet kell megtalálni a fában. A két tört, amelynek mediánjaként megtaláltuk, határolja a keresett intervallumot. Az alábbiakban Gerencsér Balázs ábrájának egy tipográfiailag módosított változatán mutatjuk be a felkutatását a fában. Induljunk el az egyik kezdőpontból, és mindig a felé lépjünk tovább: ha az éppen érintett szám nagyobb, mint , akkor balra, ha pedig kisebb, akkor jobbra lépjünk a fában (3. ábra).
3. ábra A a és az mediánjaként adódott, a keresett intervallum tehát . 2. A redukált törtek fenti származtatásával áll szoros kapcsolatban a 0 és 1 közé eső törtek Farey-sorozatokba történő elrendezése. Erről olvashatunk többek között ‐ a már idézett könyv 119‐120. oldalán, továbbá a KöMaL 1999/1. és 2. számában megjelent Holló-Szabó Ferenc: A Riemann-függvényről című cikkében. -edrendű Farey-sorozatnak nevezzük és -nel jelöljük a 0 és 1 közötti olyan redukált törtek növekvően rendezett sorozatát, amelyek nevezője nem nagyobb, mint . Például | | -et megkapjuk, ha -ből indulva mindannyiszor beszúrjuk a mediánokat, valahányszor a nevező nem nagyobb, mint . bármely két szomszédos , elemére , így a -hez tartozó maximális intervallum két végpontja két szomszédja lesz az sorozatban. Gáspár-Merse Előd (Fazekas M. Főv. Gyak. Gimn., 12. o.t.) ezzel a módszerrel kereste meg a szóban forgó intervallumot.
|
|