Feladat: 2009. évi Nemzetközi Matematika Diákolimpia 13. feladata Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Tomon István 
Füzet: 2009/október, 389 - 390. oldal  PDF  |  MathML 
Témakör(ök): Nemzetközi Matematikai Diákolimpia, Számsorozatok, Számtani sorozat, Indirekt bizonyítási mód
Hivatkozás(ok):Feladatok: 2009/szeptember: 2009. é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.

Tomon István megoldása. Tekintsük a ti=si+1-si (i=1,2,...) különbségeket, és legyen j egy olyan pozitív egész, amelyre tj=min{t1,t2...} (mivel t1,t2,... pozitív egészek, létezik ilyen j). Legyen a=sj és b=sj+1, ekkor b>a a sorozat szigorú monotonitása miatt, és legyen d az ss1,ss2,... számtani sorozat differenciája. Ekkor ssj és ssj+1 ezen sorozat két egymást követő eleme, így sb-sa=d. Mivel si szigorúan monoton nő, sa<sa+1<...<sb, vagyis az sa+1-sa, sa+2-sa+1, ..., sb-sb-1 különbségek mind pozitívak, összegük sb-sa=d, s mivel b-a darab különbség létezik, a legnagyobb legalább db-a. Legyen ekkor x egy olyan pozitív egész, amelyre a≤x<b és a legnagyobb különbség sx+1-sx≥db-a. Egyenlőség csak akkor állhat fenn, ha minden különbség db-a.
Ezután nézzük az ssx és ssx+1 között lévő elemeket. Az egyszerűség kedvéért legyen sx=e, sx+1=f, ekkor sf-se=ssx+1-ssx=d, s ha nézzük az se+1-se, se+2-se+1, ..., sf-sf-1 különbségeket, akkor az f-e darab pozitív különbség, melyek összege sf-se=d. Legyen y egy olyan pozitív egész, amelyre e≤y<f és sy+1-sy a legkisebb különbség a felsoroltak között. Ekkor

sy+1-sy≤df-e=dsx+1-sx≤ddb-a=b-a,
és egyenlőség csak akkor állhat fenn, ha mindegyik különbség egyenlő, azaz se+1-se=se+2-se+1=...=sf-sf-1. Ám szükséges, hogy egyenlőség álljon fenn mindenhol, különben sy+1-sy<b-a, ami ellentmond annak, hogy b-a a legkisebb előforduló különbség az si sorozat két szomszédos eleme között. Ha egyenlőség áll fenn, az azt jelenti, hogy az sa,sa+1,...,sb sorozat egy db-a differenciájú számtani sorozatot alkot és se,se+1,...,sf is számtani sorozatot alkot, aminek b-a a differenciája.
Ezek után megmutatjuk, hogy (b-a)2=d, vagyis b-a=db-a. Az előbbiek alapján ehhez elég igazolni, hogy
sa+1-sa=se+1-se,(1)
mivel db-a=sa+1-sa és b-a=se+1-se. (1)-hez pedig elég belátni, hogy a feladatban megadott ss1+1,ss2+1,... számtani sorozat differenciája is d, mivel ekkor
|se+1-sa+1|=d⋅|(e+1)-(a+1)|=d⋅|e-a|=|se-sa|,
ami (1)-gyel ekvivalens.
Tegyük fel indirekt módon, hogy az ss1+1,ss2+1,... számtani sorozat differenciája c≠d. Nézzünk két esetet.
1. Ha c>d, akkor tetszőleges m pozitív egész esetén
ssm+1=ss1+1+(sm-s1)⋅c
és
ssm+1=ss1+(sm+1-s1)⋅d≤ss1+(d+sm-s1)⋅d=ss1+d2+(sm-s1)⋅d,
ahol az egyenlőtlenség miatt teljesül, hogy valamely r∈N+ esetén sr≤m<sm (mivel az si sorozat tetszőlegesen nagy értéket felvehet), s ekkor ssr≤sm<sm+1≤ssr+1 a szigorú monotonitás miatt, ahol ssr és ssr+1 differenciája d. Mivel si akármilyen határon túl nő, ∃m, hogy sm-s1>d2c-d, és ekkor
ssm+1-ssm+1≥ss1+1+(sm-s1)⋅c-(ss1+(sm-s1)d+d2)>>(sm-s1)⋅(c-d)-d2>0,
vagyis ssm+1>sm+1, ami ellentmondás, mivel sm+1≤sm+1.
2. Hasonlóan a c<d esetben:
ssm+1=ss1+1+(sm-s1)césssm=ss1+(sm-s1)d>(sm-s1)d.
Ekkor ha (sm-s1)>ss1+1d-c, akkor ssm-ssm+1>(sm-s1)(d-c)-ss1+1>0, vagyis ssm>ssm+1, ami ellentmondás a szigorú monotonitás miatt.
Tehát bebizonyítottuk, hogy c=d, így megkaptuk, hogy d=(b-a)2.
Ezután megmutatjuk, hogy i=1,2,... esetén si+1-si=b-a, azaz az s1,s2,... sorozat is egy számtani sorozat. Mivel a minimális különbség két szomszédos elem között b-a, így si+1-si≥b-a. Tegyük fel, hogy valamely r-re sr+1-sr>b-a. Ekkor ssr+1-ssr=d és az ssr+1-ssr,...,ssr+1-ssr+1-1 különbségek összege d, és sr+1-sr darab van, így lesz köztük egy, amelyik legfeljebb
dsr+1-sr<db-a=b-a,
vagyis az egyik különbség kisebb (b-a)-nál, ami ellentmondás.
Tehát minden különbség b-a, vagyis s1,s2,... számtani sorozatot alkot, s ezzel a feladat állítását bizonyítottuk.