KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley