Feladat: Gy.2897 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Becsei András ,  Braun Gábor ,  Burcsi Péter ,  Elek Péter ,  Fekete Zsolt ,  Fey Dániel ,  Hegedűs Viktor ,  Hegyi Barnabás ,  Izsák Ferenc ,  Kiss Zoltán ,  Kovács Baldvin ,  Lolbert Tamás ,  Nagy Katalin ,  Rózsás Balázs ,  Szádeczky-Kardoss Szabolcs ,  Szász Nóra ,  Szobonya László ,  Torma Péter ,  Tóth Csaba ,  Tóth Gábor Zsolt ,  Tóth Mariann ,  Valkó Benedek ,  Vörös Zoltán 
Füzet: 1994/december, 486 - 487. oldal  PDF  |  MathML 
Témakör(ök): Egyenlőtlenségek, Indirekt bizonyítási mód, Számsorozatok, Gyakorlat
Hivatkozás(ok):Feladatok: 1994/február: Gy.2897

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.

Elegendő az

x1≥x2≥x3

feltételt is kielégítő sorozatokkal foglalkozni. Ugyanis egy tetszőleges, a feladatban szerpelő sorozat első három tagját csökkenő sorba rendezve, a sorozat többi eleme nem változik, s mivel az új sorozat a feladatban szereplő összes feltételt teljesíti, így ha a módosított sorozat 21. eleme 0, akkor az eredetié is. Mindezeket a következő lépésekben igazolhatjuk:
Ha x1<x2, akkor legyen
x1'=x2,x2'=x1,x3'=|x1'-x2'|,...

Világos, hogy x1',x2'≤10000, valamint xj'=xi, ha j≥3. Feltehető tehát, hogy x1≥x2.
Ha x2<x3, akkor tekintsük az
x1'=x1,x2'=x3,x3'=x2,x4'=min(|x1'-x2'|,|x1'-x3'|,|x2'-x3'|),...

sorozatot. Itt x3'=x2=x1-(x1-x2)=x1'-x3', továbbá xj'=xj, ha j≥4, hiszen xj értékét az első három elem egymás közti permutálása nem befolyásolja. S mivel x1'=x1≤10000, x2'=x3≤x1≤10000, így valóban feltehetjük, hogy sorozatunkra
x1≥x2≥x3

teljesül.
Látható, hogy xi≤xi+1, ha i=1,2,...: az i=1,2 esetben ez feltevésünkből következik, a későbbiekben pedig
xi+1=min(|x1-x2|,...,|x1-xi-1|,|x2-x3|,......,|x2-xi-1|,...,|xi-2-xi-1|,|x1-xi|,...,|xi-1-xi|)=
=min(min(|x1-x2|,...,|x1-xi-1|,...,|xi-2-xi-1|),min(|x1-xi|,...,|xi-1-xi|))=
=min(xi,Ki)≤xi,aholKi=min(|x1-xi|,...,|xi-1-xi|).

Így
xi+2=min(x1-x2,...,xi-xi+1,...)≤xi-xi+1,

azaz
xi≥xi+1+xi+2,i=1,2,...

Tegyük most föl indirekt módon, hogy x21≠0. Minthogy xi nyilvánvalóan nemnegatív egész, így szükségképpen x21≥1. Ekkor viszont

x20≥x21≥1és ezutánx19≥x20+x21≥2,x18≥x19+x20≥3,

majd a továbbiakban x17≥5, x16≥8, x15≥13, x14≥21, x13≥34, x12≥55, x11≥89, x10≥144, x9≥233, x8≥377, x7≥610, x6≥987, x5≥1597, x4≥2584, x3≥4181, x2≥6765, x1≥10946>10000, ami ellentmond az
x1≤10000

feltevésnek. Az x21=0 állítást ezzel igazoltuk.
Burcsi Péter (Pápa, Türr I. Gimn., II. o. t.)
Elek Péter (Budapest, Árpád Gimn., II. o. t.) és
Szádeczky-Kardoss Szabolcs (Fazekas M. Főv. Gy. Gimn., III. o. t.) dolgozata alapján

Megjegyzés. Az xi-kre vonatkozó alsó becsléseinket a
b0=b1=1,b2=b0+b1=2,...,bj=bj-1+bj-2

sorozat adta, amelyet Fibonacci-féle sorozatnak neveznek.