Problem A. 521. (December 2010)

A. 521. A. 521. There are given a positive integer m and an infinite sequence a₁<a₂<... of positive integers such that a_k $\le$ mk holds for infinitely many indices k. Prove that there exist positive integers b₁,...,b_m with the property that every integer can be written as a_i-a_j+b_k where i,j are positive integers and 1 $\le$ k $\le$ m.

(5 pont)

Deadline expired on January 10, 2011.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

5 students sent a solution.

5 points: Backhausz Tibor, Frankl Nóra, Nagy 235 János, Nagy 648 Donát.

2 points: 1 student.

Problems in Mathematics of KöMaL, December 2010

5 students sent a solution.
5 points:	Backhausz Tibor, Frankl Nóra, Nagy 235 János, Nagy 648 Donát.
2 points:	1 student.

Already signed up?
New to KöMaL?