A B. 4443. feladat (2012. április)

B. 4443. Adott két sorozat, az elemeik pozitív egészek: a₁,a₂,...,a_n és b₁,b₂,...,b_k, továbbá a_ik és b_jn. Mutassuk meg, hogy léteznek olyan 0i₁<i₂n és 0j₁<j₂k egészek, amelyekre

(5 pont)

A beküldési határidő 2012. május 10-én LEJÁRT.

Megoldás. Vezessük be az és sorozatokat (0in, 0jk). Mindkét egész számokból álló sorozat szigorúan monoton növekedő, első eleme 0, az utolsó pedig nem nagyobb, mint nk. Tekintsük az A_i+B_j alakú összegeket. Elegendő belátni, hogy ezek között van két egyenlő. Valóban, ha A_x+B_y és A_u+B_v két ilyen összeg, akkor yv, mert y=v maga után vonná azt is, hogy x=u. Feltehetjük hát, hogy y<v; ekkor x>u és A_x-A_u=B_v-B_y. Ez pedig azt jelenti, hogy a bizonyítandó állítás teljesül az i₁=u, i₂=x, j₁=y, j₂=v választással.

Szimmetria okok miatt feltehetjük, hogy A_nB_k. Tekintsük az S_i=(A_i+B_j) (0jk) sorozatokat. Így kapunk n+1 darab sorozatot, mindegyik szigorúan monoton növekedő, k+1 egész számot tartalmaz. Ezzel az A_i+B_j összegeket rendeztük sorozatokba. Minden egyes sorozatban bármely két egymást követő elem különbsége (A_i+B_j+1)-(A_i+B_j)=B_j+1-B_j=b_j+1n. Minden sorozat első eleme legfeljebb A_n és minden sorozat utolsó eleme legalább B_k, vagyis nem kisebb, mint A_n. Mindez azt jelenti, hogy minden egyes S_i sorozatnak valamelyik eleme bele kell essen az [A_n,A_n+n) intervallumba. Mivel ez az intervallum n darab egész számot tartalmaz, a sorozatok száma pedig n+1, az intervallumnak van olyan eleme, amelyik két sorozatban is benne van. Így tényleg találtunk két különböző (i,j) párt, melyekhez tartozó A_i+B_j összegek megegyeznek.

Statisztika:

4 dolgozat érkezett.
5 pontot kapott:	Janzer Olivér, Kabos Eszter, Viharos Andor, Zilahi Tamás.

A KöMaL 2012. áprilisi matematika feladatai