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