Feladat: F.2260 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Barla F. ,  Böröczky K. ,  Csere K. ,  Danyi P. ,  Erdős 205 J. ,  Feledi György ,  Fodor L. ,  Horváth 718 I. ,  Kántor Zs. ,  Kapos L. ,  Kappelmayer H. ,  Kiss 352 Gy. ,  Simonyi G. ,  Szegedy P. ,  Umann Gábor ,  Öreg E. Zs. 
Füzet: 1980/december, 213 - 214. oldal  PDF  |  MathML 
Témakör(ök): Számsorozatok, Feladat
Hivatkozás(ok):Feladatok: 1980/május: F.2260

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.

Mondjuk jónak az (xn-1,xn) párt a sorozatban, ha xn-1≥xn. A jó párok első tagját azok magasságának, második tagjukat a mélységüknek fogjuk nevezni. Addig megyünk előre a sorozatban, amíg a mélység nullára nem süllyed. Közben figyelni fogjuk a magasságok változását, ennek megkönnyítése érdekében kezdetben azt is feltesszük, hogy a mélység 1-nél nagyobb.
Legyen tehát xn-1≥xn>1. Ebben az esetben

xn+1=xn-1-xn,(2)
és az (xn,xn+1) pár akkor lesz újra jó, ha xn-1≤2xn. Különben
xn+2=xn+1-xn,(3)
tehát az (xn+1,xn+2) pár már biztosan jó. Az utóbbi esetben xn-nel, tehát legalább kettővel csökken a pár magassága. Az első esetben xn-1 helyett xn lesz a magasság, az tehát csak akkor marad változatlan, ha közben a mélység nullára csökken.
Amíg tehát a mélység 1 felett marad, addig egy jó párt egy vagy két lépésben ismét jó pár követ, és közben a magasság rendre vagy legalább 1-gyel vagy legalább 2-vel csökken.
Vizsgáljuk meg most azt az esetet, amikor (xn-1,xn) ugyan jó pár, de benne xn=1. Most is igaz (2), és ha xn+1>0, akkor (3) is. Ha itt xn+2>0 is teljesül, akkor érdemes tovább mennünk:
xn+3=xn+1-xn+2=xn,
most tehát (xn+2,xn+3) is jó pár, és a magassága 2-vel kisebb (xn-1,xn) magasságánál. Ha tehát a mélység 1-gyel egyenlő, ez három lépésben visszatér, és közben a magasság 2-vel csökken (feltéve persze, hogy közben nem értük el a 0-t).
Ezek alapján azt kapjuk, hogy ha (x0,x1) jó pár, és (xn,xn+1) az első olyan jó pár a sorozatban, amelyben xn+1≤1, akkor
x0≥xn+n.

Ha xn+1=0, akkor n<x0<1000 miatt készen is vagyunk, különben pedig xn=2k+ε,ε≤1. Mint láttuk, most 3k lépésben a magasság ε-ra csökken, tehát legkésőbb 1+(3k+ε) lépésben elérjük a nullát. Mivel
n+3k+ε≤n+32(2k+ε)≤32(n+xn)≤32x0<1499,
ebben az esetben igaz a feladat állítása.
Vizsgáljuk meg végül azt az esetet, amikor x0<x1, vagyis (x0,x1) nem jó pár. Ekkor ugyan x2=x1-x0 miatt már (x1,x2) jó pár lesz, tehát legfeljebb egy lépést veszthetünk, ez azonban éppen elegendő ahhoz, hogy a feladat állítása már ne legyen igaz, mint ahogy azt az x0=998,x1=999 eset mutatja, amikor is x1500 az első, nullával egyenlő tag a sorozatban. A feladat állítása tehát csak úgy igaz, ha benne az ,,1500-adik tag előtt'' helyett ,,legkésőbb x1500-ig''-et mondunk.
 
 Umann Gábor (Budapest, Fazekas M. Gyak. Gimn., IV. o. t.)