Problem B. 4443. (April 2012)
B. 4443. a1,a2,...,an és b1,b2,...,bk are two given sequences with positive integer terms with aik and bjn. Show that there are integers 0i1<i2n and 0j1<j2k 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 Ai+Bj alakú összegeket. Elegendő belátni, hogy ezek között van két egyenlő. Valóban, ha Ax+By és Au+Bv 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 Ax-Au=Bv-By. Ez pedig azt jelenti, hogy a bizonyítandó állítás teljesül az i1=u, i2=x, j1=y, j2=v választással.
Szimmetria okok miatt feltehetjük, hogy AnBk. Tekintsük az Si=(Ai+Bj) (0jk) sorozatokat. Így kapunk n+1 darab sorozatot, mindegyik szigorúan monoton növekedő, k+1 egész számot tartalmaz. Ezzel az Ai+Bj összegeket rendeztük sorozatokba. Minden egyes sorozatban bármely két egymást követő elem különbsége (Ai+Bj+1)-(Ai+Bj)=Bj+1-Bj=bj+1n. Minden sorozat első eleme legfeljebb An és minden sorozat utolsó eleme legalább Bk, vagyis nem kisebb, mint An. Mindez azt jelenti, hogy minden egyes Si sorozatnak valamelyik eleme bele kell essen az [An,An+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ó Ai+Bj ö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