A B. 4312. feladat (2010. december)

B. 4312. Egy társaságban mindenki 5 másik embert ismer (az ismeretségek kölcsönösek). Két embert kineveznek csapatkapitánynak, akik felváltva választanak egy-egy embert a csapatukba, amíg a társaság minden tagja csapattag nem lesz. Bizonyítsuk be, hogy a végén az egyik csapaton belül biztosan ugyanannyi ismeretség lesz, mint a másik csapaton belül.

Javasolta: Hubai Tamás és Király Zoltán

(3 pont)

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

Megoldás. Ha a társaságban $\displaystyle n$ ember van, akkor ők összesen $\displaystyle 5n$ embert ismernek. Mivel minden egyes ismeretség két embert feltételez, ez a szám megegyezik a kölcsönös ismeretségek számának kétszeresével, vagyis $\displaystyle n=2k$ páros szám. Ez azt jelenti, hogy a választás végén mindkét csapatban ugyanannyi ($\displaystyle k$) tag lesz. Mindkét csapatra igaz tehát, hogy tagjai összesen $\displaystyle 5k$ embert ismernek. Ha a két csapat között összesen $\displaystyle m$ kölcsönös ismeretség áll fenn, akkor gondolatmenetünk szerint mindkét csapaton belül

$\displaystyle \frac{5k-m}{2}$

lesz az ismeretségek száma.

Statisztika:

112 dolgozat érkezett.
3 pontot kapott:	77 versenyző.
2 pontot kapott:	25 versenyző.
1 pontot kapott:	5 versenyző.
0 pontot kapott:	2 versenyző.
Nem versenyszerű:	3 dolgozat.

A KöMaL 2010. decemberi matematika feladatai