Feladat: Gy.2112 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Birkás Gy. ,  Boros 966 Z. ,  Bortel L. ,  Bujdosó 419 L. ,  Csikós A. ,  Grőbler T. ,  Hraskó A. ,  Jamrik F. ,  Kós G. ,  Magyar P. ,  Marosvári 531 Zs. ,  Megyesi G. ,  Pál G. ,  Pintér Gabriella ,  Ribényi Á. ,  Somogyi 196 A. ,  Szabó Sz. ,  Szkaliczki T. ,  Werner P. ,  Zsigri G. 
Füzet: 1983/október, 69 - 71. oldal  PDF file
Témakör(ök): Függvényegyenletek, Számelméleti függvények, Gyakorlat
Hivatkozás(ok):Feladatok: 1983/március: Gy.2112

Van-e olyan, a nem-negatív egész számokon értelmezett f függvény, melyre minden nem-negatív n esetén
a) f(f(n))=n+1,
b) f(f(n))=2n?

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. Mivel minden nem‐negatív egész n-re f(n) eleme az f függvény értelmezési tartományának, azért mind az a), mind a b) esetben f csak nem‐negatív egész értékeket vehet fel.
a) Tegyük fel, hogy létezik ilyen f, és legyen f(0)=a. Ekkor a feltételt rendre a 0, a, 1, a+1, 2, a+2, ... számokra alkalmazva kapjuk, hogy

f(a)=f(f(0))=1,f(1)=f(f(a))=a+1,f(a+1)=f(f(f(1))=2f(2)=f(f(a+1))=a+2,f(a+a-1)=f(f(a-1))=a,f(a)=f(f(a+a-1))=a+a.
Így egyrészt f(a)=1, másrészt f(a)=a+a, ami lehetetlen, hiszen a nem‐negatív egész. Így az a) esetben a kérdéses függvény nem létezik.
b) Ilyen függvény viszont van, például az a függvény, amit a következőképpen definiálunk:
f(0)=0,f(2k(4m+1))=2k(4m+3),f(2k(4m+3))=2k+1(4m+1).


Mivel minden pozitív egész egyértelműen írható föl 2kp alakban, ahol p páratlan, k pedig nem‐negatív egész, azért f-et valóban (egyértelműen) megadtuk. Ez az f teljesíti a b) feltételt:
 

Ha n=0, akkor f(f(0))=f(0)=0=20,
Ha n=2k(4m+1) alakú, akkor f(f(n))=f(2k(4m+3))=2k+1(4m+1)= =2n.
 


Végül ha n=2k(4m+3) alakú, akkor
 

 f(f(n))=f(2k+1(4m+1))=2k+1(4m+3)=2n.
 


Több eset nincs, a feladatot megoldottuk.
 

II.megoldás. a b) feladatra. Meghatározzuk az összes, a feltételeket kielégítő f függvényt. Először is, f különböző helyeken nem vehet fel azonos értékeket. Ugyanis ha f(a)=f(b), akkor
2a=f(f(a))=f(f(b))=2b
alapján a=b.
Másodszor, f(0)=0. Valóban, ha f(0)=a, akkor f(a)=f(f(0))=20=0, így
a=f(0)=f(f(a))=2a,
amiből a=0. Ez egyúttal azt is jelenti, hogy f a pozitív egész helyeken pozitív egész értékeket vesz föl.
A 2n=f(f(n)) feltételt kétszer alkalmazva
f(2n)=f(f(n))=2f(n),(1)
tehát elegendő f értékét a páratlan helyeken megadnunk, azokból a páros helyeken felvett értékek (1) ismételt alkalmazásával adódnak.
Legyen most p1 egy páratlan szám. Ha f(p)=q páratlan, mondjuk azt, hogy a p párja q, s ekkor f(q)=f(f(p))=2p. Ha pedig f(p) páros, mondjuk f(p)=2q, akkor (1) szerint
2f(q)=f(2q)=f(f(p))=2p,
azaz f(q)=p. Mivel (1) alapján f páros helyeken páros értékeket vesz fel, és f(q) páratlan, azért q is páratlan, és q-nak a párja p. Így minden páratlan szám valamelyik párnak vagy első, vagy második tagja, s természetesen egyetlen szám sem lehet egyszerre két párban.
Így ha f teljesíti a b)-ben előírt követelményt, akkor a pozitív páratlan egészek feloszthatók olyan (p0,q0); (p1,q1); ... párokba, hogy (mindjárt (1)-et is felhasználva)
f(0)=0,f(2kpi)=2kqi;f(2kqi)=2k+1pi(2)


(i, k nem‐negatív egészek).
Fordítva, akárhogyan is osztjuk párokba a pozitív páratlan egészeket, a (2) által definiált f függvény teljesíti az f(f(n))=2n összefüggést.
Ezzel leírtuk az összes megfelelő függvényt. Az előző megoldásban megadott függvény a pk=4k+1, qk=4k+3 párbaosztásból adódik.
 

Megjegyzés. A feladatot nagyon sokan félreértették, ugyanis megfeledkeztek arról, hogy f mindkét esetben csak egész számokon van értelmezve, és így f(n)-nek is egésznek kell lennie. Ez zárja ki a kézenfekvő n+1/2, illetve 2n megoldásokat.