Feladat: 1979. évi Nemzetközi Matematika Diákolimpia 23. feladata Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 1979/szeptember, 4. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorikus geometria síkban, Teljes indukció módszere, Nemzetközi Matematikai Diákolimpia

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.

Legyen A és E egy szabályos nyolcszög két átellenes csúcsa. Egy béka az A csúcsból kiindulva kezd ugrálni. A nyolcszög bármely csúcsából ‐ az E-t kivéve ‐ a mellette levő egyik csúcsba ugorhat. Ha az E csúcsba ér, akkor megáll, és ott marad.
Legyen an a pontosan n ugrásból álló különböző utak száma.

 

Bizonyítsa be, hogy a2n-1=0, a2n=12(xn-1-yn-1), n=1,2,3,..., ahol x=2+2 és y=2-2.
 

Megjegyzés: Egy pontosan n ugrásból álló út a csúcsoknak olyan P0,P1,...,Pn sorozata, amely eleget tesz az alábbi feltételeknek:
 

I. P0=A, Pn=E;
II. minden, 0≤i≤n-1 egyenlőtlenséget kielégítő i-re Pi különbözik E-től;
III. minden, 0≤i≤n-1 egyenlőtlenséget kielégítő i-re Pi és Pi+1 szomszédos csúcsok.