A B. 5000. feladat (2019. január)

B. 5000. Adott $\displaystyle 4999$ különböző egész szám, az egyik a $\displaystyle 42$. Igazoljuk, hogy kiválasztható közülük néhány, amelyek összege osztható $\displaystyle 5000$-rel.

(4 pont)

A beküldési határidő 2019. február 11-én LEJÁRT.

Megoldás. Jelölje a számokat $\displaystyle a_1,a_2,\dots,a_{4999}$ és tekintsük az $\displaystyle s_1:=a_1,s_2:=a_1+a_2,\dots,s_{4999}:=a_1+a_2+\dots+a_{4999}$ összegeket. Ha ezek között szerepel 5000-zel osztható, akkor készen vagyunk. Ha az összegek közül kettő, mondjuk $\displaystyle s_i$ és $\displaystyle s_j$ ($\displaystyle i<j$ mellett) ugyanannyi maradékot ad 5000-zel osztva, akkor $\displaystyle s_j-s_i=a_{i+1}+a_{i+2}+\dots+a_j$ megfelelő, 5000-zel osztható összeg. Vagyis minden esetben készen vagyunk, kivéve, ha az $\displaystyle s_i$ összegek 5000-es maradéka $\displaystyle 1,2,\dots,4999$ valamilyen sorrendben, vagyis minden nemnulla maradék pontosan egyszer fordul elő. Legyen $\displaystyle s_1':=a_2$. Az $\displaystyle s_1',s_2,\dots,s_{4999}$ összegekkel az előző gondolatmenet megismételhető, vagyis találunk megfelelő összeget, kivéve, ha ezek között is minden nemnulla maradék pontosan egyszer fordul elő. Ha még nem vagyunk készen, akkor viszont $\displaystyle s_1=a_1$ és $\displaystyle s_1'=a_2$ ugyanannyi maradékot adnak 5000-zel osztva, hiszen mind $\displaystyle s_1$, mind $\displaystyle s_1'$ azt a nemnulla maradékot adja, ami nem szerepel a másik 4998 összeg maradéka között. Azt kaptuk tehát, hogy az állítás biztosan teljesül, ha $\displaystyle a_1$ és $\displaystyle a_2$ maradéka különböző. Mivel a számokat tetszőlegesen átbetűzhetjük, valójában kiderült, hogy készen vagyunk, ha nem ad mind a 4999 szám ugyanannyi maradékot. Utóbbi esetben viszont mindegyikük 42 maradékot kell adjon mod 5000, így közülük 2500-at kiválasztva megfelelő összeget kapunk (hiszen $\displaystyle 5000\mid 42\cdot 2500$). Ezzel a feladat állítását igazoltuk.

II. Megoldás. Legyen a számok között szereplő páros számok száma $\displaystyle t\geq 1$. Ekkor a páratlanok száma $\displaystyle 4999-t$, vagyis párba állítva őket képezhetünk belőlük $\displaystyle \left[ \frac{4999-t}{2} \right]$ kéttagú összeget. Ezeket, és a páros számokat (mint egytagú összegeket) tekintve összesen $\displaystyle t+\left[ \frac{4999-t}{2} \right]\geq t+\frac{4999-t}{2}-\frac{1}{2}=\frac{t}{2}+2499\geq 2500$ páros összeget kapunk (hiszen $\displaystyle t\geq 1$ a feltétel szerint). Legyen $\displaystyle b_1=2c_1,\dots,b_{2500}=2c_{2500}$ az előbbi (egy-, vagy kéttagú) páros összegek közül 2500. A $\displaystyle c_1,c_1+c_2,\dots,c_1+c_2+\dots+c_{2500}$ összegeket tekintve az 1. Megoldásban is alkalmazott gondolatmenetet követve most azt kapjuk, hogy van néhány a $\displaystyle c_i$ számok között, melyek összege 2500-zal osztható. A megfelelő $\displaystyle b_i$-k összege tehát 5000-zel osztható, és mivel ez az összeg egyben különböző $\displaystyle a_j$-k összegeként is előáll, ez igazolja a feladat állítását.

Statisztika:

69 dolgozat érkezett.
4 pontot kapott:	Apagyi Dávid, Argay Zsolt, Baski Bence, Beke Csongor, Bencsik Ádám, Biczó Benedek, Bokor Endre, Bukva Dávid, Csaplár Viktor, Dobák Dániel, Fleiner Zsigmond, Fraknói Ádám, Fülöp Anna Tácia, Füredi Erik Benjámin, Geretovszky Anna, Győrffi Ádám György, Győrffy Ágoston, Győrffy Johanna, Hámori Janka, Hegedűs Dániel, Jánosik Áron, Jánosik Máté, Kerekes Boldizsár, Kovács 129 Tamás, Laki Anna, Lovas Márton, Mátravölgyi Bence, Miszler Levente, Nagy 551 Levente, Nagy Nándor, Németh Regő, Nguyen Bich Diep, Noszály Áron, Pooya Esmaeil Akhoondy, Rareș Polenciuc, Reimann Kristóf, Sándor Péter, Sebestyén Pál Botond, Soós 314 Máté, Stomfai Gergely, Szabó 417 Dávid, Telek Zsigmond , Terjék András József, Tiderenczl Dániel, Tóth 057 Bálint, Tóth 827 Balázs, Várkonyi Zsombor, Weisz Máté, Zsigri Bálint.
3 pontot kapott:	6 versenyző.
2 pontot kapott:	4 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	8 versenyző.

A KöMaL 2019. januári matematika feladatai