Feladat: F.2370 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Ákosfai Z. ,  Alberti G. ,  Balázs Z. ,  Böröczky K. ,  Danyi P. ,  Engländer J. ,  Erdős 228 L. ,  Hetyei G. ,  Holbok I. ,  Kántor Cs. ,  Lenkó Cs. ,  Magyar Á. ,  Megyesi G. ,  Mohay T. ,  Papp 193 G. ,  Sigray I. ,  Simák Gy. ,  Szabó E. ,  Szabó Endre ,  Szederkényi Edit ,  Törőcsik J. ,  Wágner P. A. ,  Weisz F. ,  Zieger B. 
Füzet: 1983/március, 107 - 108. oldal  PDF file
Témakör(ök): Gráfelmélet, Indirekt bizonyítási mód, Feladat, Logikai feladatok
Hivatkozás(ok):Feladatok: 1982/május: F.2370

Egy teremben 11-en vannak. Tudjuk, hogy akárhogyan is választunk ki közülük kettőt, a többiek közül pontosan egy ismeri mindkettőjüket. Mutassuk meg, hogy van a teremben olyan, aki mindenki mást ismer.

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.

Ábrázoljuk a társaság tagjait az ábécé nagy betűivel jelölt pontokkal és ismertségüket ‐ melyet kölcsönösnek feltételezünk ‐ e pontokat összekötő szakaszokkal. Tehát két pont akkor és csak akkor van összekötve, ha az általuk reprezentált személyek ismerősök. A feltételek miatt ebben a pontszakasz rendszerben biztosan van legalább egy AB szakasz és van egy C pont úgy, hogy AC és BC szakasz is létezik.
Megmutatjuk, hogy az összes többi pont össze van kötve A, B, C valamelyikével.
Tegyük fel ugyanis, hogy D nem ismeri A, B, C egyikét sem. Ekkor létezik E, aki A-t és D-t ismeri. A feltétel szerint E nincs összekötve sem B-vel, sem C-vel, hiszen ekkor lenne a társaságban két olyan ember, akit nem pontosan egy másik ismer. (Pontok és szakaszok nyelvén ezt úgy fogalmazhatjuk, hogy négyszög nem jöhet létre, hiszen ennek átellenes csúcsai nem felelnek meg a feltételeknek.) Ugyanilyen okból létezik F, aki B-t és D-t ismeri, valamint G, aki C-t és D-t ismeri (1. ábra).

 
1. ábra
 
2. ábra
 
3. ábra

 
Az ábrán szereplő hét ember között további ismeretségek nem lehetnek, mert bármely két pontot összekötő szakaszt behúzva, négyszög keletkezne. Vannak továbbá olyan H, I, J, K, L, M tagjai, a társaságnak, akik rendre az (A,E), (B,F), (C,G), (E,D), (F,D), (G,D) párok közös ismerősei (2. ábra). Előző megjegyzésünk alapján e hat ember bármelyike különbözik az 1. ábrán szereplő hét ember bármelyikétől. Belátjuk, hogy H, I, J, K, L, M-mel valóban hat egymástól különböző embert jelöltünk. Elég a H=I, H=K, K=L eseteket kizárni. A 3. ábráról leolvasható, hogy pont-szakasz rendszerünkben bármelyik egyenlőség fennállása esetén négyszög keletkezne.
Mivel indirekt feltevésünkből az következett, hogy a társaságnak legalább 13 tagja van, állíthatjuk, hogy mindenki ismeri A, B, C valamelyikét.
Megmutatjuk, hogy az összes többi pont A, B, C közül ugyanazzal van összekötve.
 
4. ábra
 
5. ábra
Tegyük fel ugyanis ennek ellenkezőjét, tehát hogy DB és EA szakaszok léteznek. Mivel minden pont az A, B, C közül pontosan eggyel van összekötve, léteznie kell egy F-nek, aki E-t és D-t ismeri. Ez az F azonban nem lehet összekötve sem A-val, sem B-vel, sem C-vel, mivel ekkor az (F,B); (F,A); (F,C) párokat két tagja is ismerné a társaságnak (4. ábra).
Így tehát mindenki ismeri A, B, C egyikét, pl. A-t. Az 5. ábrán látható, hogy létezik ilyen, a feltételeknek megfelelő társaság.
 

 Szabó Endre (Budapest, Fazekas M. Gyak. Gimn., IV. o. t.)
 
Megjegyzés. A feladat állítása nemcsak 11, hanem bármilyen páratlan számú tagból álló társaságra igaz. Ennek a "barátság-tétel'' néven ismert állításnak bizonyítása egyáltalán nem könnyű.