A B. 4592. feladat (2014. január)

B. 4592. Hány fős lehet az a társaság, amelyben mindenkinek pontosan 3 ismerőse van, és két embernek pontosan akkor van közös ismerőse, ha egymást nem ismerik?

(5 pont)

A beküldési határidő 2014. február 10-én LEJÁRT.

Megoldásvázlat. Az ismeretségi rendszert szemléltessük egy irányítatlan gráffal. Mivel most minden csúcs fokszáma 3, így a csoport páros. Bármely két ember vagy ismeri egymást, vagy van közös ismerősük. Tehát ha kiválasztunk valakit, akkor annak 3 ismerőse van, és ennek a 3 ismerősnek van fejenként még 2 másik ismerőse (akik egymástól nem feltétlenül különböznek). Ez legfeljebb \(\displaystyle 1+3+6=10\) főt jelent. Tehát a létszám 2, 4, 6, 8 vagy 10 lehet.

Ebből a 2 és a 4 nem lehetséges, a 6, a 8 és a 10 pedig igen:

Statisztika:

157 dolgozat érkezett.
5 pontot kapott:	74 versenyző.
4 pontot kapott:	7 versenyző.
3 pontot kapott:	6 versenyző.
2 pontot kapott:	10 versenyző.
1 pontot kapott:	52 versenyző.
0 pontot kapott:	6 versenyző.
Nem versenyszerű:	2 dolgozat.

A KöMaL 2014. januári matematika feladatai