Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

Problem B. 4443. (April 2012)

B. 4443. a1,a2,...,an és b1,b2,...,bk are two given sequences with positive integer terms with ai\lek and bj\len. Show that there are integers 0\lei1<i2\len and 0\lej1<j2\lek such that a_{i_1+1}+\ldots +a_{i_2}=b_{j_1+1}+\dots +b_{j_2}.

(5 pont)

Deadline expired on May 10, 2012.


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

Megoldás. Vezessük be az A_i=\sum_{\alpha=1}^i a_\alpha és B_j=\sum_{\beta=1}^j b_\beta sorozatokat (0\lei\len, 0\lej\lek). 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 y\nev, 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 An\leBk. Tekintsük az Si=(Ai+Bj) (0\lej\lek) 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+1\len. 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