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 a₁<a₂<... sorozat úgy, hogy a_k $\le$ mk teljesül végtelen sok k indexre. Igazoljuk, hogy léteznek olyan b₁,...,b_m pozitív egészek, amelyekre minden egész szám előáll a_i-a_j+b_k alakban, ahol i, j pozitív egészek és 1 $\le$ k $\le$ m.

(5 pont)

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

Megoldás (Nagy Donát megoldása). Ha a b₁,b₂,...,b_m egészekre teljesülnek a feladat feltételei, esetleg azt leszámítva, hogy a b_i-knek pozitívnak kell lennie, akkor tetszőleges T $\in$ Z mellett ugyanez igaz a b₁+T,b₂+T,...,b_m+T egészekre is, hiszen az, hogy minden egész előáll a_i-a_j+b_k alakban, ekvivalens azzal, hogy minden egész előáll a_i-a_j+b_k+T alakban. Így a b_i-k pozitivitására vonatkozó feltétel elhagyásával a bizonyítandóval ekvivalens állítást kapunk, hiszen ha b₁,b₂,...,b_m tetszőleges megfelelő egészek, egy mindannyiuknál kisebb T egészt választva a b₁-T,b₂-T,...,b_m-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 a₁<a₂<... pozitív egészekből álló sorozatra, amelyre a_k $\le$ mk végtelen sok k-ra, nincsenek megfelelő b₁,b₂,...,b_m (nem feltétlenül pozitív) egészek.

Teljes indukcióval igazoljuk, hogy ha 0<r $\le$ m+1, akkor vannak olyan c₁,c₂,...,c_r egészek, amelyekre a {c_i+a_j: j $\in$ N} halmazok (i=1,2,...,r) páronként diszjunktak.

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

Tegyük fel, hogy az állítás r $\le$ m-re igaz a c₁,c₂,...,c_r számokkalé megmutatjuk, ekkor r+1-re is igaz. Legyen b₁=c₁, b₂=c₂, ..., b_r=c_r, b_r+1=b_r+2=...=b_m=0. Az indirekt feltevésünk szerint ezek a b_i-k nem megfelelőek, így van egy olyan szám, amely nem írható a_i-a_j+b_k alakban. Válasszuk ez a számot c_r+1-nek. Ha valamely 1 $\le$ k $\le$ r-re {c_r+1+a_j: j $\in$ N} $\cap$ {c_k+a_i: i $\in$ N} $\ne$ Ø, akkor vanak olyan i,j $\in$ N indexek, hogy c_r+1+a_j=c_k+a_i, tehát c_r+1=a_i-a_j+c_k=a_i-a_j+b_k; de ez ellentmond annak, hogy c_r+1 nem írható a_i-a_j+b_k alakban. Azt már az indukciós feltevésből tudjuk, hogy 1 $\le$ k,l $\le$ r, k $\ne$ l-re {c_k+a_i: i $\in$ Z} $\cap$ {c_l+a_j: j $\in$ Z}=Ø, így viszont az állítás valóban igaz (r+1)-re is.

Tekintsük az r=m+1-hez kapott c₁,c₂,...,c_m+1 értékeket! Legyen C=max {|c₁|,|c₂|,...,|c_m+1|} és k>2C olyan, hogy a_k $\le$ m^.k (végtelen sok ilyen k van, így van 2C-nél nagyobb is). Ekkor a {c_i+a_j: j $\in$ N} halmazok (i=1,2,...,m+1) páronként diszjunktak, így a c_i+a_j értékek, ahol 1 $\le$ i $\le$ m+1 és 1 $\le$ j $\le$ k, páronként különbözőek. Mivel ezen (m+1)k egész mindegyike legalább 1-C és legfeljebb a_k+C, így (m+1)k $\le$ a_k+C-(1-C)+1 $\le$ mk+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

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

Már regisztráltál?
Új vendég vagy?