Feladat: Pontversenyen kívüli P.129 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Breuer Péter ,  Fulmer László 
Füzet: 1973/október, 70 - 71. oldal  PDF file
Témakör(ök): Gráfelmélet, Játékelmélet, játékok, Konstruktív megoldási módszer, Pontversenyen kívüli probléma
Hivatkozás(ok):Feladatok: 1972/február: Pontversenyen kívüli P.129

Bizonyítsuk be, hogy ha egy (véges) társaságban mindenki mindenkivel egy pingpongmérkőzést játszott, akkor van a társaságnak olyan A tagja, hogy a társaság bármely (további) B tagjára a következű két állítás közül legalább az egyik igaz :
 

a) A legyőzte B-t.
 

b) Van a társaságnak olyan C tagja, hogy A legyőzte C-t és C legyőzte B-t.

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.

A társaságban mindenkiről felírjuk, hányszor győzött, legyen e számok legnagyobbika g. Ilyen van, mert a társaság véges, és tagjainak számát n-nel jelölve gn-1. Azt mutatjuk meg, hogy A szerepére alkalmas az a tag, aki g-szer győzött (ill. ha többen is vannak ilyenek, akkor bármelyikük alkalmas).
Tulajdonképpen csak az olyan további B tagokhoz kell a b)-ben kívánt C létezését belátnunk, kiket A nem győzött le. (n=2 esetében ilyen nincs, mert g=1, ekkor csak az a) állítás igaz nyilvánvalóan; tovább tehát föltesszük, hogy legalább 3-an játszottak.) Így B győzte le A-t, mert befejezett pingpong mérkőzés eredménye nem döntetlen; de nem győzte le mindazokat, akiket A legyőzött, mert különben (g+1) győzelme volna. Van tehát az A által legyőzöttek között, akit B nem győzött le, tehát ő győzte le B-t; ez megfelel C szerepére.

 

 Fulmer László (Székesfehérvár, Teleki Blanka Gimn.)
 

II. megoldás. Egy megfelelő A személyt a következő "szűréssel'' keresünk ki az együtt ülő társaságból. Felszólítunk találomra valakit, hogy távozzon és vigye magával mindazokat, akiket legyőzött. Nevezzük ezt egy brigádnak és a felszólított személyt a brigád vezetőjének. (Az is lehetséges persze, hogy a brigád csak a vezetőből áll.) Távozásuk után ezt annyiszor és addig ismételtetjük, míg a terem kiürül. Ez előbb-utóbb bekövetkezik, hiszen a társaság véges. Ekkor az utoljára távozott brigád vezetője megfelelő A-ként (mindjárt A-nak nevezzük).
Ha ugyanis a társaság egy B tagja maga is brigádvezetőként ment ki ‐ tehát előbb, mint A ‐, akkor nem győzte le A-t, tehát kettőjük közt az a) állítás teljesül. Akkor is ez a helyzet, ha B az A brigádjában ment ki. Ha pedig B egy korábban távozott brigádban ment ki mint legyőzött, akkor a brigádvezetője megfelel C-ként, tehát teljesül a b) állítás. (Az is lehetséges, hogy a társaság bizonyos B tagjaira az a), b) állítások mindegyike teljesül.)
 

 Breuer Péter (Eger, Gárdonyi G. Gimn.)
 

Megjegyzések. 1. Az itt kiválasztott A személy nem tartozik szükségképpen a legsikeresebb játékosok közé. Egyetlen győzelemmel is megfelelhet, ha azt győzte le, aki rajta kívül mindenkit legyőzött (természetesen ha van ilyen; egyébként csak egy lehet).
Fordítva: B is ott lehet a legtöbb győzelmet elért játékosok közt.
2. Bizonyítható az állítás teljes indukcióval is.
3. Végtelen sok tagú társaságot gondolva az állítás nem igaz.