Feladat: B.4759 Korcsoport: 16-17 Nehézségi fok: könnyű
Megoldó(k):  Sal Kristóf ,  Simon Dániel Gábor 
Füzet: 2016/október, 406 - 407. oldal  PDF file
Témakör(ök): Feladat, Kombinatorika, Logikai feladatok
Hivatkozás(ok):Feladatok: 2016/január: B.4759

Egy kerek asztal körül négy férfi és négy nő ül. Bizonyítsuk be, hogy van négy szomszédos ember, akik közt ugyanannyi a nő, mint a férfi.

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.

 
I. megoldás. Tegyük fel az állítással ellentétben, hogy nincs négy ilyen ember. Ekkor mindegyik ,,szomszédos'' négyesben vagy férfiból, vagy nőből van több. Előfordulhat-e, hogy mindegyik négyesben férfiból van több? Ha ez így lenne, akkor a 8 darab ,,szomszédos'' négyes mindegyikében legalább három férfi szerepelne, vagyis összesen legalább 38=24-et számolnánk. Viszont mindegyik részvevő pontosan 4 négyesben szerepel, így a férfiak száma legalább 6 lenne. Ugyanez a helyzet adódna, ha mindegyik négyesben több lenne a nő. Tehát van olyan négyes is, amelyben több a nő és van olyan is, amelyben több a férfi. Két négyes legyen szomszédos, ha eggyel balra vagy jobbra lépünk. Két ilyen szomszédos négyesben a férfiak és a nők száma is csak 1-gyel térhet el egymástól, vagy változatlan marad. A fentiek alapján ahhoz, hogy egy ,,férfi többségű'' négyesből eljussunk egy ,,nő többségű'' négyesig, közben legalább egyszer lennie kell olyan átmenetnek, amikor a férfiak és a nők száma megegyezik.
 
II. megoldás. Tegyük fel, hogy a feladat állítása nem igaz. Ekkor nyilvánvalóan bármely négy szomszédos ember között több van az egyik neműből. Számozzuk meg az embereket az ábra szerint.

 
 

Ekkor az 1, 2, 3, 4 sorszámú emberek között az egyik nemből (pl. férfiból) több van. Ebből következik, hogy a szomszédos 2, 3, 4, 5 csoportban is több a férfi, mint a nő. Ellenkező esetben a férfiak számának 2-vel kellene legalább csökkennie, hiszen minimum 3 férfi helyett maximum 1 lehetne, ez viszont lehetetlen, mert férfiak és nők száma is legfeljebb eggyel változhat szomszédos négyesre lépve. Ezt a gondolatsort folytatva bármely szomszédos négyesnek legalább 3 férfit kell tartalmazni. Ebből látható, pl. az első megoldás alapján, hogy legalább 6 férfi és legfeljebb 2 nő lenne a társaságban. Ellentmondásra jutottunk, tehát az eredeti állítás igaz.