Feladat: 10.22.
* Egy elektronikus levelezőtársaságnak 2004 tagja van. Közülük néhányan személyesen is ismerik egymást (az ismeretség kölcsönös). Bizonyítsa be, hogy a 2004 tag két csoportba osztható úgy, hogy a csoportokon belül személyes ismeretségek számának összege nem több, mint a két csoport tagjai közötti ismeretségek száma! (OKTV, 2005)
Megoldás: 10.22
Osszuk valahogy két csoportba az embereket. Ha az egyik csoportban találunk egy olyan embert, aki a saját csoportjából többet ismer, mint a másik csoportból, akkor tegyük át a másik csoportba. Ezzel a csoportok közötti ismeretségek száma nő, a csoportokon belüli ismeretségek száma csökken.
Az eljárást addig folytatjuk, amíg találunk ilyen embert. Mivel a csoportok közötti személyes ismeretségek száma mindig nő, egy embert kétszer nem mozgatunk, így legkésőbb 2004 csere után az eljárás véget ér. A végállapotban viszont minden ember legalább annyi embert ismer a másik csoportból, mint a sajátjából. Jelöljük azt a számot, ahányat az
x ember a saját csoportjából ismer,
ds
(x)-szel, azt a számot pedig, ahányat a másik csoportból ismer,
dm
(x)-szel. Tudjuk, hogy az utóbbi legalább akkora, mint az előbbi. Adjuk össze az előbbieket minden emberre, ekkor a csoportokon belüli ismeretségek kétszeresét kapjuk Euler tétele szerint. Másrészt adjuk össze a
dm
(x) számokat, ekkor a csoportok közötti ismeretségek kétszeresét kapjuk. Vagyis éppen azt kapjuk, hogy a csoportokon belüli ismeretségek számának összege nem több, mint a két csoport tagjai közötti ismeretségek száma. Azt kellett bizonyítani, hogy van ilyen csoportosítás.