Feladat: B.3712 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Boskovits Dávid ,  Kónya Gábor 
Füzet: 2005/február, 87 - 88. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorikai leszámolási problémák, Részgráfok, Feladat
Hivatkozás(ok):Feladatok: 2004/március: B.3712

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. Osszuk a vendégeket két csoportba aszerint, hogy 4-nél kevesebb vagy több ismeretséget szereztek. Ekkor az első csoport négy tagja összesen 1+2+3+3=9, a többiek pedig 5+6+6+6=23 ismeretséget szereztek az este folyamán.
A vendégség során kialakult ismeretségeket különböztessük meg aszerint, hogy azonos vagy pedig különböző csoportba tartozók kötötték-e: hívjuk az előbbieket belső, utóbbiakat pedig külső ismeretségnek. Egy csoport tagjai által kötött ismeretségek összege a külső kapcsolatok számának és a belső kapcsolatok kétszeresének az összege, hiszen a csoporton belül egy belső ismeretség 2, egy külső pedig 1 ismeretséget jelent. Nyilvánvaló továbbá, hogy a két csoport külső ismeretségeinek a száma egyenlő. Ekkor

9=2B1+K,(1)23=2B2+K.(2)

A két egyenlet különbségét 2-vel osztva B2-B1=7 adódik. Egy négytagú társaságban viszont legfeljebb 6 ismeretség köthető, ezért 0≤B1,B2≤6, tehát B2-B1=7 nem lehetséges. A kapott ellentmondás mutatja, hogy valamelyik résztvevő tévedett.
 
Megjegyzés. Ha a társaság tagjait pontokkal, a köztük fennálló ismeretségeket pedig a pontokat összekötő szakaszokkal ábrázoljuk, akkor egy úgynevezett gráfhoz jutunk. Az alábbi megoldás ezt a szemléltetést és a gráfelmélet szóhasználatát követi.
 
II. megoldás. Hagyjuk el a gráfból az elsőfokú csúcsot a belőle kiinduló éllel együtt. Ha az él másik végpontja eredetileg 6-odfokú, akkor a kapott 7 csúcsú gráfban az egyes csúcsok fokszámai rendre: 2, 3, 3, 5, 5, 6, 6.
Ebben a gráfban a két 6 fokszámú csúcsból minden további csúcsba megy él (1. ábra). Ezt a két csúcsot és a belőlük kilépő éleket elhagyva olyan 5 csúcsú gráfhoz jutunk, ahol az egyes csúcsok fokszáma rendre: 0, 1, 1, 3, 3.
 

 
1. ábra
 

A 0 fokú csúcsot elhagyva négy csúcs marad, köztük két harmadfokú. A másik két csúcs tehát legalább másodfokú (2. ábra), ami nem teljesül.
 

 
2. ábra
 

Meg kell még vizsgálnunk azt az esetet, amikor az elsőnek elhagyott él másik végpontja legfeljebb 5-ödfokú. Ekkor a megmaradt gráfban három 6-odfokú csúcs van. Mind a négy további csúcs ezekkel össze van kötve, tehát mindegyikük legalább harmadfokú (3. ábra). Ez viszont nem lehetséges, ugyanis mielőtt egyikük 1-gyel csökkent volna, a négy fokszám értéke 2, 3, 3 és 5 volt. Nem létezik tehát az adott tulajdonságú gráf, valamelyik résztvevő hibás értéket közölt.
 

 
3. ábra