Problem B. 4162. (March 2009)

B. 4162. 60 bars of chocolate are distributed among a class of 30 students. Everyone gets at least one but no one gets 31 bars. Prove that it is possible to select a group of students who received a total of exactly 30 bars of chocolate together.

(4 pont)

Deadline expired on April 15, 2009.

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

Megoldás: Az osztály egyes tagjai által kapott csokik számát jelölje nem növekvő sorrendben a₁,a₂,...,a₃₀. A feltételek szerint tehát

$1\le a_{30}\le a_{29}\le \ldots\le a_{1}\le 30, \quad a_1+a_2+\ldots+a_{30}=60.$

Azt kell belátni, hogy az a_i számok közül kiválasztható néhány úgy, hogy az összegük 30. Ez nyilvánvaló, ha mindegyik szám 2. Tegyük fel ennek megfelelően, hogy a₃₀=1. Jelölje k a legkisebb olyan számot, amelyre teljesül, hogy az a_i számok közül a k legnagyobb összege nagyobb, mint 30. Más szóval, k azt a 2 és 30 közé eső számot jelöli, amelyre

$S_{k-1}=a_1+a_2+\ldots+a_{k-1}\le 30,\quad S_k=a_1+a_2+\ldots+a_k\ge 31.$

Az $a_{k+1},\ldots,a_{30}$ számok közül, melyek összege legfeljebb 29, az 1-esek számát jelölje x. A fennmaradó 30-k-x szám mindegyike legalább 2, ezért x+2(30-k-x) $\le$ 29, ahonnan x $\ge$ 31-2k adódik. A monotonitási feltétel miatt ka_k $\le$ S_k, ahonnan

$S_{k-1}=S_k-a_k\ge\frac{k-1}{k}S_k\ge 31-\frac{31}{k}$

adódik. Ezért 2 $\le$ k $\le$ 14 esetén

$0\le 30-S_{k-1}\le \frac{31}{k}-1<31-2k\le x,$

vagyis $a_1,a_2,\ldots,a_{k-1}$ a fennmaradó számok közül megfelelő számú 1-essel kiegészítve megfelelő lesz. Ha k $\ge$ 15, akkor vegyük figyelembe azt is, hogy 30-S_k-1 egész szám. Így a fenti becslés továbbra is érvényes első fele, valamint az a₃₀=1 feltevés alapján 30-S_k-1 $\le$ 1 $\le$ x adódik, tehát a bizonyítást ugyanúgy befejezhetjük, mint az előbb.

Statistics:

73 students sent a solution.

4 points: Ágoston Péter, Ágoston Tamás, Bálint Dániel, Barczel Nikolett, Beke Lilla, Bóra Eszter, Bősze Zsuzsanna, Csizmadia Luca, Czeller Ildikó, Dinh Hoangthanh Attila, Éles András, Énekes Péter, Fonyó Dávid, Frankl Nóra, Hoksza Zsolt, Horowitz Gábor, Janosov Milán, Janzer Olivér, Keresztfalvi Tibor, Kiss 232 Dóra, Kiss 902 Melinda Flóra, Korondi Zénó, Kovács 729 Gergely, Kovács 999 Noémi, Lenger Dániel, Lovas Lia Izabella, Maknics András, Mester Márton, Mészáros András, Nagy 111 Miklós, Nagy 648 Donát, Paripás Viktor, Perjési Gábor, Somogyi Ákos, Szórádi Márk, Tuan Nhat Le, Tubak Dániel, Varga 171 László, Weisz Ágoston, Weisz Gellért, Zelena Réka, Zsakó András.

3 points: Balla Attila, Botos Csongor, Welsz Edit.

2 points: 8 students.

1 point: 9 students.

0 point: 10 students.

Unfair, not evaluated: 1 solutions.

Problems in Mathematics of KöMaL, March 2009

73 students sent a solution.
4 points:	Ágoston Péter, Ágoston Tamás, Bálint Dániel, Barczel Nikolett, Beke Lilla, Bóra Eszter, Bősze Zsuzsanna, Csizmadia Luca, Czeller Ildikó, Dinh Hoangthanh Attila, Éles András, Énekes Péter, Fonyó Dávid, Frankl Nóra, Hoksza Zsolt, Horowitz Gábor, Janosov Milán, Janzer Olivér, Keresztfalvi Tibor, Kiss 232 Dóra, Kiss 902 Melinda Flóra, Korondi Zénó, Kovács 729 Gergely, Kovács 999 Noémi, Lenger Dániel, Lovas Lia Izabella, Maknics András, Mester Márton, Mészáros András, Nagy 111 Miklós, Nagy 648 Donát, Paripás Viktor, Perjési Gábor, Somogyi Ákos, Szórádi Márk, Tuan Nhat Le, Tubak Dániel, Varga 171 László, Weisz Ágoston, Weisz Gellért, Zelena Réka, Zsakó András.
3 points:	Balla Attila, Botos Csongor, Welsz Edit.
2 points:	8 students.
1 point:	9 students.
0 point:	10 students.
Unfair, not evaluated:	1 solutions.

Already signed up?
New to KöMaL?