|
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 fogott a legtöbbször kezet (vagy legalábbis a legtöbbször kezet fogók egyike), és jelöljük kézfogásainak a számát -mel. Az az ember, akikkel kezet fogott, csak a többi () emberrel (köztük -mel) foghatott kezet, hiszen ha közülük bármely kettő egymással kezet fogna, -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 kezet fogott, összesen legfeljebb kézfogást kaphatunk: embernél fejenként legfeljebb kézfogást. A többieknél (köztük -nél is) legfeljebb kézfogást számíthatunk, és mivel ők -en vannak, összesen ismét legfeljebb -et kapunk. Ez összesen , de így minden kézfogást kétszer számoltunk, a kézfogások száma tehát legfeljebb lehet. Ez akkor maximális, ha , tehát a társaságban legfeljebb kézfogásra kerülhetett sor. Pontosan ennyi kézfogás volt, ha például nő és 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 -nak nincs különösebb szerepe, általában tagú társaságban kézfogásra kerülhet sor, ahol . 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 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. |
|