Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem C. 1071. (March 2011)

C. 1071. The forum of this journal on the internet has exactly 1000 registered members. Each member sends an e-mail to one other member. Prove that it is possible to select a group of 334 members such that within the group no one sent an e-mail to anyone else.

(5 pont)

Deadline expired on April 11, 2011.


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

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.


Statistics:

94 students sent a solution.
5 points: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 points: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 points:18 students.
2 points:22 students.
1 point:20 students.
0 point:9 students.

Problems in Mathematics of KöMaL, March 2011