Feladat: N.129 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Frenkel Péter ,  Kun Gábor ,  Lippner Gábor ,  Lukács László ,  Mátrai Tamás ,  Pap Gyula 
Füzet: 1997/október, 419. oldal  PDF file
Témakör(ök): Számsorozatok, Teljes indukció módszere, Ellenpélda, mint megoldási módszer a matematikában, Nehéz feladat
Hivatkozás(ok):Feladatok: 1997/február: N.129

Az a1, a2, ... sorozat pozitív egészekből áll, és tetszőleges n-re ann. Bizonyítsuk be, hogy létezik olyan nem konstans számtani sorozat, amelynek minden eleme előáll az (an) sorozat első néhány elemének előjeles összegeként, azaz ±a1±a2±...±ak alakban. Mutassuk meg, hogy az állítás nem marad igaz akkor, ha csak azt követeljük meg, hogy az (an/n) sorozat korlátos legyen.

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.

a) Legyen sn=a1+a2+...+an. Megmutatjuk, hogy ha sn páros, illetve páratlan, akkor minden, a [-sn;sn] intervallumbeli páros, illetve páratlan szám előáll ±a1±a2±...±an alakban. Ebből a feladat első része azonnal következik, mert vagy minden páros szám, vagy minden páratlan egész szám előáll néhány an előjeles összegeként.
Állításunk igaz n=1 esetén, mert a feltételek miatt s1=a1=1. Tegyük fel, hogy igaz n=k-ra;  bebizonyítjuk n=k+1 esetén is. Az indukciós feltevés alapján
(±a1±...±ak-1)-ak alakban előáll az összes [-sk-1-ak;sk-1-ak]-beli,
(±a1±...±ak-1)+ak alakban pedig az összes [-sk-1+ak;sk-1+ak]-beli, megfelelő paritású szám. De sk-1+ak=sk, sk-1-ak(k-1)1-k=-1 miatt ez a két intervallum a 0 kivételével biztosan tartalmazza az összes -sk és sk közötti egész számot. Ha a 0 nem szerepel az intervallumokban, az csak úgy lehet, ha a1=a2=...=ak-1=1 és ak=k, akkor viszont sk=2k-1 páratlan, tehát a 0-t nem is kell előállítanunk.

 

b) Elég egy ellenpéldát mutatnunk. Legyen an=100n, ha n  10-hatvány, ellenkező esetben legyen an=1. Erre a sorozatra ann100.
Ha 10kn<10k+1, akkor tetszőleges előjelek esetén
||±a1±a2±...±an|-10010k|(a1+a2+...+a10k-1)+(a10k+1+...+an)==100(100+101+...+10k-1)+n-k-1<10010k-19+10k+1<2210k.
Ez azt jelenti, hogy |±a1±a2±...±an| csak az Ik=(7810k;12210k) intervallumban lehet.
Ezek az intervallumok diszjunktak, mert
7810k+1-12210k=65810k,
sőt az intervallumok közötti hézagok mérete minden határon túl nő. Ezért tetszőleges számtani sorozatnak van olyan eleme, amelyet egyik intervallum sem tartalmaz.
 
Megjegyzés. Akik csak a feladat első felét oldották meg, 2 pontot kaptak.