Feladat: B.3875 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Almási Gábor András ,  Sümegi Károly 
Füzet: 2006/december, 542 - 543. oldal  PDF file
Témakör(ök): Gráfelmélet, Skatulyaelv, Teljes indukció módszere, Logikai feladatok, Feladat
Hivatkozás(ok):Feladatok: 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.)

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

I. 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 2n16 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, van a társaságban valaki, aki mind a 15-öt ismeri. A szóban forgó n résztvevővel együtt ez n+1 ember, akik közül bármely kettő ismeri egymást.

 
II. megoldás. Nyissunk az összejövetelen két termet, és tetszés szerint küldjünk be 15 embert az egyikbe, a maradék 16-ot pedig a másikba. Ezután mindig abból a teremből küldünk át egyvalakit a másikba, ahol éppen 1-gyel többen vannak, a következő módon. A feladat feltétele szerint van a társaságnak olyan tagja, aki mindenkit ismer a 15 fős teremből. Kiválasztunk egy ilyen embert, és átküldjük a 16 fős teremből a másikba. Vegyük észre, hogy ha valaki már egyszer átkerült egy terembe, akkor ott mindenkit ismerni fog (azt is, aki csak később kerül oda, hiszen az csak úgy jöhet át, ha a teremből mindenkit ismer). Ha valaki visszakerül oda, ahol eredetileg volt, akkor ‐ az eddigiek szerint ‐ mindkét teremből mindenkit ismer, azaz az összejövetelen résztvevők mindegyikét ismeri. Tehát elég megmutatnunk, hogy biztosan lesz valaki, aki kétszer cserél termet. Mivel összesen 31-en vannak, azért (a skatulya-elv szerint) az első 32 átküldés során lesz olyan ember, aki kétszer is átkerül másik terembe, és éppen ezt kellett bizonyítanunk.