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. 4162. feladat (2009. március)

B. 4162. Egy 30 fős osztály tagjai között kiosztunk 60 darab csokit úgy, hogy mindenki kap csokit, de senki sem kap 31 darabot. Bizonyítsuk be, hogy - mielőtt még bárki is fogyasztott volna a csokikból - kiválasztható az osztályból egy olyan csoport, akiknél összesen pontosan 30 db csoki van.

(4 pont)

A beküldési határidő 2009. április 15-én LEJÁRT.


Megoldás: Az osztály egyes tagjai által kapott csokik számát jelölje nem növekvő sorrendben a1,a2,...,a30. 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 ai 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 a30=1. Jelölje k a legkisebb olyan számot, amelyre teljesül, hogy az ai 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)\le29, ahonnan x\ge31-2k adódik. A monotonitási feltétel miatt kak\leSk, 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\lek\le14 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\ge15, akkor vegyük figyelembe azt is, hogy 30-Sk-1 egész szám. Így a fenti becslés továbbra is érvényes első fele, valamint az a30=1 feltevés alapján 30-Sk-1\le1\lex adódik, tehát a bizonyítást ugyanúgy befejezhetjük, mint az előbb.


Statisztika:

73 dolgozat érkezett.
4 pontot kapott:Á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 pontot kapott:Balla Attila, Botos Csongor, Welsz Edit.
2 pontot kapott:8 versenyző.
1 pontot kapott:9 versenyző.
0 pontot kapott:10 versenyző.
Nem versenyszerű:1 dolgozat.

A KöMaL 2009. márciusi matematika feladatai