Van-e olyan 21 tagú társaság, amelyben mindenkinek 7 ismerőse van, ha az ismeretség mindig kölcsönös?

Ilyenkor össze kell számolni, hogy hány ismertség van összesen a társaságon belül: mindenki 7 embert ismer, ez 21*7 ismertség, viszont minden ismertség kölcsönös, tehát az A ismeri B ismertséget A-nál és B-nél is számoltuk, így ezt el kell osztani kettővel… Hm.

Szerintem gondold végig.

Ezt a feladatot felfoghatjuk egy gráfnak, ahol a csúcsok az emberek, két csúcsot akkor kötünk össze éllel, hogyha 2 ember ismeri egymást. Ebben a gráfban a feladat szerint mindenkinek 7 ismerőse van, vagyis minden csúcs fokszáma 7. Azt sem nehéz bizonyítani, hogy akárhogyan rajzolunk fel egy gráfot, a fokszámok összege mindig páros lesz; ennek az oka az, hogy ha veszünk egy üres gráfot, akkor minden csúcs fokszáma 0, tehát összegük 0, ha behúzunk egy élt, akkor az él két végpontjának fokszáma 1-gyel nő, tehát a fokszámösszeg 2 lesz. Aztán 4, 6, 8, stb., tehát mindig páros.

Esetünkben a fokszámösszeg 7+7+...+7=21*7=147, ami nem páros, következésképp egy 21-tagú társaságban nem lehet mindenkinek pontosan 7 ismerőse. Ha 20 vagy 22 lenne (vagy legalább 8 és páros), akkor kivitelezhető lehetne a feltétel.

Igen, értem én, hogy hülye dolog a nyelv, de hogy nekem ismerősöm valaki, az általában magában foglalja, hogy ő nem én vagyok. Hasonlóan osztálytársa se lehet valaki magának, hiába jár ő is ugyanabba az osztályba, mint ő.

Gondold végig. Ha igazad lenne, akkor mikor egyedül sétálsz az utcán, és megkérdezik, hogy hány ismerősöddel vagy, azt kéne mondanod, hogy 1-gyel, de nem ezt mondod, hanem hogy nincs ott egy ismerősöd se.