Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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

B. 4443. Adott két sorozat, az elemeik pozitív egészek: a1,a2,...,an és b1,b2,...,bk, továbbá ai\lek és bj\len. Mutassuk meg, hogy léteznek olyan 0\lei1<i2\len és 0\lej1<j2\lek egészek, amelyekre


a_{i_1+1}+\ldots +a_{i_2}=b_{j_1+1}+\ldots +b_{j_2}.

(5 pont)

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


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.


Statisztika:

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

A KöMaL 2012. áprilisi matematika feladatai