Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az A. 521. feladat (2010. december)

A. 521. Adott egy m pozitív egész és egy pozitív egészekből álló, végtelen a1<a2<... sorozat úgy, hogy ak\lemk teljesül végtelen sok k indexre. Igazoljuk, hogy léteznek olyan b1,...,bm pozitív egészek, amelyekre minden egész szám előáll ai-aj+bk alakban, ahol i, j pozitív egészek és 1\lek\lem.

(5 pont)

A beküldési határidő 2011. január 10-én LEJÁRT.


Megoldás (Nagy Donát megoldása). Ha a b1,b2,...,bm egészekre teljesülnek a feladat feltételei, esetleg azt leszámítva, hogy a bi-knek pozitívnak kell lennie, akkor tetszőleges T\inZ mellett ugyanez igaz a b1+T,b2+T,...,bm+T egészekre is, hiszen az, hogy minden egész előáll ai-aj+bk alakban, ekvivalens azzal, hogy minden egész előáll ai-aj+bk+T alakban. Így a bi-k pozitivitására vonatkozó feltétel elhagyásával a bizonyítandóval ekvivalens állítást kapunk, hiszen ha b1,b2,...,bm tetszőleges megfelelő egészek, egy mindannyiuknál kisebb T egészt választva a b1-T,b2-T,...,bm-T egészek pozitívak lesznek, és szintén megfelelnek.

Tegyük fel indirekt módon, hogy egy adott m pozitív egészre és a1<a2<... pozitív egészekből álló sorozatra, amelyre ak\lemk végtelen sok k-ra, nincsenek megfelelő b1,b2,...,bm (nem feltétlenül pozitív) egészek.

Teljes indukcióval igazoljuk, hogy ha 0<r\lem+1, akkor vannak olyan c1,c2,...,cr egészek, amelyekre a {ci+ajj\inN} halmazok (i=1,2,...,r) páronként diszjunktak.

r=1-re például c1=0 megfelelő.

Tegyük fel, hogy az állítás r\lem-re igaz a c1,c2,...,cr számokkalé megmutatjuk, ekkor r+1-re is igaz. Legyen b1=c1, b2=c2, ..., br=cr, br+1=br+2=...=bm=0. Az indirekt feltevésünk szerint ezek a bi-k nem megfelelőek, így van egy olyan szám, amely nem írható ai-aj+bk alakban. Válasszuk ez a számot cr+1-nek. Ha valamely 1\lek\ler-re {cr+1+ajj\inN}\cap{ck+aii\inN}\neØ, akkor vanak olyan i,j\inN indexek, hogy cr+1+aj=ck+ai, tehát cr+1=ai-aj+ck=ai-aj+bk; de ez ellentmond annak, hogy cr+1 nem írható ai-aj+bk alakban. Azt már az indukciós feltevésből tudjuk, hogy 1\lek,l\ler, k\nel-re {ck+aii\inZ}\cap{cl+ajj\inZ}=Ø, így viszont az állítás valóban igaz (r+1)-re is.

Tekintsük az r=m+1-hez kapott c1,c2,...,cm+1 értékeket! Legyen C=max {|c1|,|c2|,...,|cm+1|} és k>2C olyan, hogy ak\lem.k (végtelen sok ilyen k van, így van 2C-nél nagyobb is). Ekkor a {ci+ajj\inN} halmazok (i=1,2,...,m+1) páronként diszjunktak, így a ci+aj értékek, ahol 1\lei\lem+1 és 1\lej\lek, páronként különbözőek. Mivel ezen (m+1)k egész mindegyike legalább 1-C és legfeljebb ak+C, így (m+1)k\leak+C-(1-C)+1\lemk+2C, de ez ellentmond k>2C-nek. Emiatt az ellentmondás miatt az indirekt feltevésünk téves volt, de így a feladat állítása igaz.


Statisztika:

5 dolgozat érkezett.
5 pontot kapott:Backhausz Tibor, Frankl Nóra, Nagy 235 János, Nagy 648 Donát.
2 pontot kapott:1 versenyző.

A KöMaL 2010. decemberi matematika feladatai