KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

B. 3875. There were 31 people at a party. For any 15 of them, there is a further member of the group who knows all of them. (Acquaintances are mutual.) Prove that there is a guest of the party who knows all the others.

(5 points)

Deadline expired on 15 February 2006.


Google Translation (Sorry, the solution is published in Hungarian only.)

Megoldás: Elég azt bizonyítani, hogy van a társaságban 16 ember úgy, hogy közülük bármely kettő ismeri egymást. Ekkor ugyanis közülük valakinek ismernie kell a fennmaradó 15 résztvevő mindegyikét; a társaságnak ez a tagja tehát mindenkit ismer.

Ennek igazolásához pedig n szerinti indukcióval azt bizonyítjuk, hogy minden 2\len\le16 esetén van a társaságban n ember úgy, hogy közülük bármely kettő ismeri egymást. Ez n=2 esetén nyilvánvaló, ha pedig 2\len<16 esetén már tudjuk, hogy van a társaságban n megfelelő ember, akkor őket további 15-n résztvevővel kiegészítve, tekintsük a társaságnak egy olyan tagját, aki mind a 15-öt ismeri. A szóban forgó n résztvevővel együtt ez az ember a társaságnak n+1 olyan tagját alkotja, akik közül bármely kettő ismeri egymást.


Statistics on problem B. 3875.
73 students sent a solution.
5 points:Almási 270 Gábor András, Balambér Dávid, Blázsik Zoltán, Bogár 560 Péter, C. Szabó Bence, Dudás László, Farkas Ádám László, Fegyverneki Tamás, Gresits Iván, Györgyi Péter, Halász Máté, Honner Balázs, Károlyi Márton, Kiss 243 Réka, Kovács 111 Péter, Kunovszki Péter, Lovász László Miklós, Mészáros Gábor, Nagy 235 János, Nagy 314 Dániel, Németh 007 Zsolt, Peregi Tamás, Pirkó Dániel, Sümegi Károly, Szabó 108 Tamás, Szalóki Dávid, Szécsényi Ágnes, Szilágyi 987 Csaba, Szirmai Péter, Szolnoki Lénárd, Szűcs Gergely, Tossenberger Anna, Udvari Balázs, Varga 111 Péter, Véges Márton, Zieger Milán.
4 points:Kovács 129 Péter.
3 points:5 students.
2 points:3 students.
1 point:17 students.
0 point:11 students.


  • Problems in Mathematics of KöMaL, January 2006

  • Támogatóink:   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