Feladat: 1978. évi Nemzetközi Matematika Diákolimpia 13. feladata Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 1978/október, 50 - 52. oldal  PDF  |  MathML 
Témakör(ök): Függvényegyenletek, Számsorozatok, Fibonacci-sorozat, Teljes indukció módszere, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):Feladatok: 1978/szeptember: 1978. évi Nemzetközi Matematika Diákolimpia 13. feladata

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. Tekintsük az 1 és g(n) közti egész számokat. Ezek mindegyike vagy f-nek vagy g-nek valamilyen helyen felvett értékeként adódik ki. Mégpedig g értékeként n szám, g(1),g(2),...,g(n);ag(n)-1=f(f(n)) alapján f értékeként f(n) szám, f(1),f(2),...,f(n). Ezzel minden 1 és g(n) közti számot pontosan egyszer kapunk meg, tehát
g(n)=f(n)+n(*)
Ebből adódik, hogy f(1)=1 (hiszen vagy f(1)-nek vagy g(1)-nek kell 1-nek lennie és g(1)=f(1)+1>1), innen g(1)=2. Hasonlóan f(2)=3 (hiszen g(2)=f(2)+2>f(1)+2=3). Ezek után elkezdhetjük kitölteni az alábbi táblázatot. Minden természetes számnak pontosan egyszer kell benne szerepelnie. Így ha a táblázatot valameddig már kitöltöttük, a következő oszlop ,,f sorába'' a legkisebb, eddig még nem szereplő számnak, ,,g sorába'' pedig a (*) képlet szerinti számnak kell kerülnie.
 


-12345678910111213141516...234235236237238239240f13468911121416171921222425...378380381383385386388g25710131518202326283134363941...612615617620623625628
 
A táblázatból leolvasható a végeredmény: f(240)=388.
 

II. megoldás. A (*) összefüggés alapján
f(f(n))=f(n)+n-1.(**)
Ebből f(3)=f(f(2))=f(2)+2-1=4, f(4)=4+3-1=6, f(6)=9, f(9)=14, f(14)=22, f(22)=35, f(35)=56, f(56)=90, és így g(35)=56+35=91. Mivel minden g(n) érték valamilyen f(k) érték rákövetkezője, azért nem lehet g(36) értéke 92, következésképpen f(57)=92. Innen f(92)=92+56=148, f(148)=239, f(239)=386. Másrészt g(148)=239+148=387, ezért az előbbi okoskodás alapján f(240)=388.
 

III. megoldás. Legyen a0=1, és an+1+1=f(an+1)(n=0,1,2,...). Ekkor a1=2 és a (**) képlet szerint
an+2+1=f(an+1+1)=f(f(an+1))=an+1+1+an
azaz az {an} sorozat éppen a Fibonacci-sorozat. Teljes indukcióval megmutatjuk, hogy
f(an+x)=an+1+f(x)1≤x≤an-1esetén.(***)
Ehhez előbb megjegyezzük, hogy f(y) értéke y-nál annyival több, ahány ,,g'' van 1 és f(y) között. Ennek értéke viszont megegyezik a maximális olyan m-mel, amelyre g(m)=f(f(m))+1≤f(y), ami pontosan akkor áll, ha f(m)<y. Így
f(an+x)=an+x+m,
ahol m a legnagyobb olyan szám, amelyre f(m)<an+x.
Mivel f(an-1+1)=an+1≤an+x és f(an+1+1)=an+2+1>an+x, azért an-1<m≤an+1 és így alkalmazhatjuk az indukciós feltevést:
f(m)=f(an-1+m-an-1)=an+1(m-an-1),
azaz m a legnagyobb olyan szám, amelyre f(m-an-1)<x. Ez viszont éppen azt jelenti, hogy f(x)=x+(m-an-1), vagyis
f(an+x)=an+x+m=an+an-1+f(x),
ahogyan azt állítottuk.
A teljes indukció befejezéséhez még (***)-ot például a=1-re ellenőrizni kell: f(a1+1) =a1+f(1), s ez valóban teljesül.
Végül minden 1-nél nagyobb pozitív szám egyértelműen írható fel 1+ai1+ai2+... alakban, ahol ij≤ij+1+2,ij≥0. Ekkor (***) alapján
f(1+al1+al2+...)=1+ai1+1+ai2+1+...,
ami ismét indukcióval igazolható. Esetünkben a Fibonacci-sorozat 240-nél kisebb tagjai: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, továbbá 240=1+1+5+233, és így f(1+1+5+233)= 1+2+8+377=388.
 

Megjegyzés. A megoldásokban feltételeztük, hogy létezik a feltételeket kielégítő f és g függvény. Annyit bizonyítottunk, hogy ha létezik, akkor f(240)=388 lehet csak. A megoldásokból az is kiderült, hogy legfeljebb egy ilyen f és q függvény létezhet.
 

IV. megoldás. Legyen α=(5+1)/2,f(n)=[nα] és g(n)=[nα2]. Állítjuk, hogy f és g eleget tesz a feladat összes feltételének. Így (feltéve, hogy f és g egyértelműen meghatározott) f(240)=[240α]=[1205+120]=388.
Először is világos, hogy f és g szigorúan monoton növekszik, hiszen α>1 és α2>1. Másrészt 1/α+1/α2=1, α és α2 irracionális, és így f és g értékkészlete minden egész számot pontosan egyszer ad ki (lásd Skljarszkij‐Csencov‐Jaglom: Válogatott feladatok és tételek az elemi matematika köréből, 1. kötet, 108. feladat). Így csak a
g(n)=f(f(n))+1
összefüggést kell igazolnunk. De g(n)≠f(n)), hiszen f és g értékkészletének nincs közös eleme. Másrészt [αn]<αn, azaz
[[αn]α]≤[α2n]f(f(n))≤g(n)


α>1 és 1=α2-α alapján az αn<α+[αn]=α+(α2-α)[αn] egyenlőtlenséget α-val osztva és átrendezve
n+[αn]<α[αn]+1,
amiből
g(n)=[α2n]=[(1+α)n]==n+[αn]≤[α[αn]+1]=f(f(n))+1.