Kezdőlap


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ő $(\frac{a}{b}, \frac{c}{d}, \frac{e}{f})$ számhármasra $b c - a d = d e - c f = b e - a f = 1$ . Ennek következménye, hogy $\frac{a}{b} < \frac{c}{d} < \frac{e}{f}$ , 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 $α < q < β$ , 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 $β < q < γ$ , akkor az $α$ számot kell letörölnünk, és a $β$ , $γ$ számokkal kell folytatnunk a műveletet;

*	3. Ha $q = β$ , akkor találtunk egy olyan számhármast, amelynek középső eleme $q$ . Tovább folytatni nem szabad, mert az előbbi okok miatt semelyik újabb mediáns nem lehet $q$ .

A fentiek alapján a

q

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

q

-t, azaz véges sok lépésben véget ér.
Legyen

q = \frac{s}{t}

, az

n

-edik lépésben keletkező számhármas

(\frac{a_{n}}{b_{n}}, \frac{c_{n}}{d_{n}}, \frac{e_{n}}{f_{n}})

. Megmutatjuk, hogy a

g_{n} = (s b_{n} - t a_{n}) + (t e_{n} - s f_{n})

sorozat szigorúan monoton fogy. Ebből a végesség következik, mert a

g_{n}

sorozat pozitív egészekből áll.

Legyen az

n

-edik számhármas

(\frac{a_{n}}{b_{n}}, \frac{c_{n}}{d_{n}}, \frac{e_{n}}{f_{n}})

, amelyben

c_{n} = a_{n} + e_{n}

és

d_{n} = b_{n} + f_{n}

.
Ekkor

\frac{a_{n}}{b_{n}} < q < \frac{c_{n}}{d_{n}}

esetén

\begin{matrix} g_{n + 1} = (s b_{n} - t a_{n}) + (t c_{n} - s d_{n}) = t e_{n} - s f_{n} < g_{n}, \end{matrix}

\frac{c_{n}}{d_{n}} < q < \frac{e_{n}}{f_{n}}

esetben pedig

\begin{matrix} g_{n + 1} = (s d_{n} - t c_{n}) + (t e_{n} - s f_{n}) = s b_{n} - t a_{n} < g_{n} . \end{matrix}

Megjegyzések. 1. A megoldás kis módosításával az is igazolható, hogy ha nem a

(\frac{0}{1}, \frac{1}{2}, \frac{1}{1})

, hanem tetszőleges

(\frac{a}{b}, \frac{a + c}{b + d}, \frac{c}{d})

számhármasból indulunk ki, akkor is tetszőleges

\frac{a}{b} < q < \frac{c}{d}

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

q

-t, bebizonyítható a lépések egyszerű megfordításával is. Ha

q = \frac{s}{t}

és ez a tört nem egyszerűsíthető, akkor egyértelműen léteznek olyan

a, b, c, d

nemnegatív egész számok, amelyekre

b s - a t = e t - f s = b c - a d = 1

, ezekkel a számokkal az utolsó számhármas csak

(\frac{a}{b}, \frac{s}{t}, \frac{c}{d})

lehet. Nem nehéz bebizonyítani, hogy egy ilyen számhármasból mindig lehet visszafelé lépni, kivéve a

(\frac{0}{1}, \frac{1}{2}, \frac{1}{1})

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

q

előállítását.
3. Ha nagyság szerint sorbarendezzük azokat a

[0,1]

-beli, nem egyszerűsíthető törteket, amelyek nevezője legfeljebb

n

, akkor az úgynevezett

n

-edik Farey-sorozatot kapjuk. Például az

5

-ödik Farey-sorozat:

\begin{matrix} \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1} . \end{matrix}

Ebben a sorozatban bármely két szomszédos

\frac{a}{b}

\frac{c}{d}

elemre

b c - a d = 1

, 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)