Feladat: A.378 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Erdélyi Márton ,  Gyenizse Gergő ,  Hujter Bálint ,  Jankó Zsuzsanna ,  Kisfaludi-Bak Sándor ,  Kónya Gábor ,  Molnár András ,  Nagy Csaba ,  Paulin Roland ,  Sümegi Károly ,  Szabó Tamás ,  Ureczky Bálint 
Füzet: 2006/január, 26 - 27. oldal  PDF file
Témakör(ök): Törtfüggvények, Euklideszi algoritmus, Konstruktív megoldási módszer, Nehéz feladat
Hivatkozás(ok):Feladatok: 2005/szeptember: A.378

Létezik-e olyan f:Q{-1,1} függvény, amelyre f(x)=-f(y), valahányszor x és y különböző racionális számok, és xy=1 vagy x+y{0,1}?

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.

Megoldás. Létezik ilyen függvény. Tetszőleges x racionális szám egyértelműen írható véges lánctört alakban:

x=a0+1a1+1a2+...+1an,
ahol a0 egész szám, az a1,...,an számok pedig pozitív egészek és an>1. A lánctörtjegyeket egyszerű mohó algoritmussal kapjuk. Az a0 csak az x egész része lehet. Ha x nem egész, akkor az 1x számot kell tovább bontanunk. Az algoritmus során a felbontandó szám számlálója és nevezője az Euklideszi algoritmusnak megfelelően csökken, ezért az eljárás biztosan véget ér.
Legyen tetszőleges racionális x-re (x) az x lánctört alakjában a törtvonalak száma (azaz a fenti n index). A lánctörtképzés szabályai szerint (x)=0, ha x egész, és (x)=(1x)+1 ha 0<x<1.
Definiáljuk az f függvényt a következőképpen.
f(0)=-1;f(x)=(-1)(x),  ha  x>0;f(x)=-(-1)(|x|),  ha  x<0.

Az (x) függvény definíciójából következik, hogy ha x pozitív racionális szám és k pozitív egész, akkor (x+k)=(x) és f(x+k)=f(x).
Igazolni kell, hogy f(1x)=-f(x), ha x0,±1. Mivel f(-x)=-f(x) és f(-1x)=-f(1x), ezt elég pozitív x-ekre belátni. Mivel x és 1x szerepe is felcserélhető, feltehető, hogy 0<x<1. Ekkor viszont (x)=(1x)+1, azaz f(1x)=-f(x).
Az f függvény definíciójából látható, hogy ha x+y=0, akkor f(x)=-f(y), kivéve az x=y=0 esetet. Ezért már csak azt kell belátni, hogy f(1-x)=-f(x), ha x12. A szimmetria miatt feltehető, hogy x>12.
Ha x>1, akkor f(x)=f(x-1)=-f(1-x), a feltétel teljesül.
Ha x=1, akkor f(x)=f(1)=1 és f(1-x)=f(0)=-1, szintén készen vagyunk.
Marad az az eset, amikor 12<x<1. Ekkor pedig
f(x)=-f(1x)=-f(1x-1)=-f(1-xx)==f(x1-x)=f(x1-x+1)=f(11-x)=-f(1-x).
Az f függvény tehát mindegyik feltételnek eleget tesz.
 
Megjegyzés. Könnyű meggondolni, hogy ha f(1) értéke adott, az a feltételek mellett az összes többi értéket meghatározza, (indukcióval a lánctört-alakban levő törtvonalak hossza szerint) ezért csak a most definiált f függvény és (-1)-szerese teljesíti a feltételeket.