 |
A B. 3875. feladat (2006. január) |
B. 3875. Egy összejövetelen 31 ember vett részt. Közülük bármely 15-höz van a társaságnak egy további tagja, aki mindegyiküket ismeri. Bizonyítandó, hogy van olyan tagja a társaságnak, aki a résztvevők mindegyikét ismeri. (Az ismeretségek kölcsönösek.)
(5 pont)
A beküldési határidő 2006. február 15-én LEJÁRT.
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
n16 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 2n<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.
Statisztika:
73 dolgozat érkezett. 5 pontot kapott: 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 pontot kapott: Kovács 129 Péter. 3 pontot kapott: 5 versenyző. 2 pontot kapott: 3 versenyző. 1 pontot kapott: 17 versenyző. 0 pontot kapott: 11 versenyző.
A KöMaL 2006. januári matematika feladatai