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

Problem B. 3875. (January 2006)

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 pont)

Deadline expired on February 15, 2006.


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

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:

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