A C. 1071. feladat (2011. március)

C. 1071. A KöMaL fórumának pontosan 1000 regisztrált tagja van. Minden tag küld egy e-mailt pontosan egy másik tagnak. Bizonyítsuk be, hogy közülük kiválaszthatunk egy olyan 334 tagú csoportot, amelyen belül senki nem küldött senkinek e-mailt.

(5 pont)

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

Megoldás. Ha mindenki pontosan egy levelet küld, akkor 1000 darab emailt küldtek összesen. A fórumozók közül válasszunk ki tetszőlegesen egy 334 tagú csoportot (A). Ha nincs olyan levél, amit valaki a csoporton belülről kapott volna, akkor megtaláltuk a feladat kívánalmának megfelelő csoportot. Ellenkező esetben nézzük a maradék 666 tagot (B). Feltehető, hogy legfeljebb 333 levelet küldtek az A csoport tagjainak, ellenekző esetben ezek közül kerül ki az a legalább 334 tagú csoport, melyben senki nem küldött levelet a másiknak. Tehát ezen levelek közül legalább 333 levél címzettje a van B-ben. Keressünk A-ban egy olyan tagot, aki A-belitől kapott levelet, és B-ben egy olyan tagot, aki B-belinek küldött levelet. Cseréljenek helyet: ezzel A-ban csökkent az A-n belül küldött levelek száma (eggyel vagy kettővel). Ezt az eljárást folytassuk addig, amíg A-ban senki nem küld senkinek levelet. Legfeljebb 333 helycserére lesz szükség, és ennyit választhatunk is B-ből.

Statisztika:

94 dolgozat érkezett.
5 pontot kapott:	Béres Bertold, Bingler Arnold, Fonyó Viktória, Gehér Péter, Gema Barnabás, Kószó 94 Eszter, Nagy 021 Tibor, Németh Klára Anna, Samu Viktor, Szőts Nóra, Tóth Endre, Végh Dávid András.
4 pontot kapott:	Baráth Dávid, Érsek Laura, Kasó Márton, Katona 100 Bálint, Kedves Máté, Madarasi Adrienn, Martinka Mátyás, Mezősi Máté, Sagmeister Ádám, Szabó 928 Attila, Szigeti Bertalan György, Varga 149 Imre Károly, Vincze Ákos.
3 pontot kapott:	18 versenyző.
2 pontot kapott:	22 versenyző.
1 pontot kapott:	20 versenyző.
0 pontot kapott:	9 versenyző.

A KöMaL 2011. márciusi matematika feladatai