Feladat: F.2105 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Blázsik Z. ,  Csikós B. ,  Erdélyi T. ,  Gát Gy. ,  Gömöry Ágnes ,  Hajnal P. ,  Horváth 619 M. ,  Kántor S. ,  Lakatos P. ,  Lukács 258 Erzsébet ,  Madi T. ,  Nagy 647 G. ,  Palásti Zsuzsanna ,  Pyber L. ,  Ráth Gy. ,  Sali A. ,  Somogyi Á. ,  Szabó 284 Sándor ,  Szegedy M. ,  Szekeres G. ,  Szendrei Gy. ,  Tálas Cs. ,  TArdos G. ,  Tengelics Erzsébet ,  Toplenszki J. ,  Varga J. ,  Winkler R. ,  Zempléni A. 
Füzet: 1978/január, 8 - 9. oldal  PDF  |  MathML 
Témakör(ök): Gráfok komplementere, Kombinatorikai leszámolási problémák, Feladat
Hivatkozás(ok):Feladatok: 1977/szeptember: F.2105

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.

Tegyük fel, hogy a társaságban M fogott a legtöbbször kezet (vagy legalábbis a legtöbbször kezet fogók egyike), és jelöljük M kézfogásainak a számát m-mel. Az az m ember, akikkel M kezet fogott, csak a többi (20-m) emberrel (köztük M-mel) foghatott kezet, hiszen ha közülük bármely kettő egymással kezet fogna, M-et hozzájuk véve három olyan embert kapnánk, akiknek a létezését a feladat kizárja.

 




Számoljuk most össze a kézfogásokat úgy, hogy mindegyiket mindkét érintett személynél számításba vesszük. Azoknál, akikkel M kezet fogott, összesen legfeljebb m(20-m) kézfogást kaphatunk: m embernél fejenként legfeljebb (20-m) kézfogást. A többieknél (köztük M-nél is) legfeljebb m kézfogást számíthatunk, és mivel ők (20-m)-en vannak, összesen ismét legfeljebb m(20-m)-et kapunk. Ez összesen 2m(20-m), de így minden kézfogást kétszer számoltunk, a kézfogások száma tehát legfeljebb m(20-m) lehet. Ez akkor maximális, ha m=10, tehát a társaságban legfeljebb 100 kézfogásra kerülhetett sor. Pontosan ennyi kézfogás volt, ha például 10 nő és 10 férfi volt a társaságban, és minden nő minden férfival kezet fogott. Ekkor bárhogy veszünk ki hármat a társaságból, van köztük két egynemű, akik nem fogtak kezet.
 

Megjegyzések. 1. Feladatunkban (és megoldásában) a 20-nak nincs különösebb szerepe, általában n tagú társaságban k(n-k) kézfogásra kerülhet sor, ahol k=[n2]. Ez a tétel Turán Páltól származik, és a gráfelmélet egyik első eredménye. Tehetünk a feladatban. három helyett is tetszőleges más számot, így azonban sokkal nehezebb kérdést kapunk.
2. A feladatra igen sok hibás megoldás érkezett. Ezekben ugyan a végeredmény többnyire helyes, mégsem fogadhattuk el őket, hiszen csak azt mutatták meg, hogy van olyan társaság, ahol 100 kézfogásra került sor, és ebből a feladat kérdésére vonatkozóan még semmilyen következtetést nem vonhatunk le.