Problem B. 4443. (April 2012)

B. 4443. a₁,a₂,...,a_n és b₁,b₂,...,b_k are two given sequences with positive integer terms with a_ik and b_jn. Show that there are integers 0i₁<i₂n and 0j₁<j₂k such that .

(5 pont)

Deadline expired on May 10, 2012.

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

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.

Statistics:

4 students sent a solution.
5 points:	Janzer Olivér, Kabos Eszter, Viharos Andor, Zilahi Tamás.

Problems in Mathematics of KöMaL, April 2012