Feladat: 1.2.
a) Az
1.1. feladatban a következő állítást kellett igazolni:
Egy kilenctagú társaságban mindenki pontosan öt másik embernek átad 100 Ft-ot. Bizonyítsuk be, hogy az ajándékozások után van két ember, akinek ugyanannyi forinttal változott a vagyona. (Arany Dániel-verseny 1990H)
Igaz-e az is, hogy vagy van három ember, akinek ugyanannyi forinttal változott a vagyona, vagy van két-két ember, akiknek ugyanannyival változott a vagyona?
b) Fogalmazzuk át gráfelméleti nyelvre az
1.1. feladatot és a fenti feladatot is!
c) Hogyan általánosítható a feladat?
Megoldás: 1.2
a) Az
1.1. feladat megoldásából indulunk ki. Ha csak egy pár ember van, akik ugyanannyi petákot kaptak, s a többi hét petákjainak száma az övékétől is, egymásétól is különböző, akkor a kapott petákok összege legfeljebb nyolccal lehet több 36-nál, ami még mindig kevesesbb 45-nél. Tehát b) állítás is igaz.
b) Gráfelméleti nyelven adott egy kilencpontú irányított gráf, amelyben nincs hurokél és többszörös irányított él (az
xy és az
yx él szerepelhet egyszerre!), továbbá minden pont kifoka öt. Azt állítjuk, hogy van két pont, amelynek a befoka egyenlő. Sőt, vagy van három pont, amelynek befoka azonos, vagy van két-két pont, amelyeknek a befoka azonos.
c) Ha adott egy
n pontú irányított gráf, amelyben nincs hurokél és többszörös irányított él, továbbá minden pont kifoka legalább
n/2, akkor van két pont, amelyek befoka egyenlő. A kifokok összege ugyanis egyenlő a befokok összegével. Ha nincs hurokél, és minden pont befoka különböző volna, akkor a befokok összege
0+1+2+…+(n-1)=n(n-1)/2 volna. De minden pont kifoka legalább
n/2, ezért a kifokok összege legalább
n2
/2>n(n-1)/2, tehát a kifokok és befokok összege nem egyezne. Ez az ellentmondás bizonyítja az állítás helyességét.
Valójában elég azt feltételezni, hogy a kifokok
átlaga nagyobb
(n-1)/2-nél, már akkor is igaz, hogy van két azonos befokú pont.