Feladat: 1954. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Balatoni Ferenc ,  Bárdos András ,  Csiszár Imre ,  Kovács László ,  Vigassy József 
Füzet: 1955/április, 103 - 105. oldal  PDF  |  MathML 
Témakör(ök): Természetes számok, Kombinatorikai leszámolási problémák, Részhalmazok, Szabályos sokszögek geometriája, Irányított gráfok, Teljes indukció módszere, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1955/január: 1954. évi Kürschák matematikaverseny 3. feladata

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. Legyen A olyan résztvevő, akinél több győzelmet senki sem aratott. Ha A nem felelne meg a feladat követelményének, akkor volna olyan B versenyző, akit sem A, sem az A által legyőzöttek nem győztek le, aki tehát mindezeket megverte, s így legalább eggyel több győzelmet aratott, mint A. Ez azonban lehetetlenség, mert A-nál több győzelmet senki sem aratott, ezért A megfelel a feladat követelményének.

 

II. megoldás. Legyen A1 a versenyzők egyike. Ha az A1 által a feladat előírása szerint végzett felsorolásban nem szerepel minden más versenyző, akkor jelöljük az általa nem említett versenyzők összességét H1-gyel. Minthogy A1 ezeket nem említette, mindegyikük megverte A1-et és az A1 által legyőzötteket. Ezért a H1 csoport minden tagja megemlíti az A1 által említetteket, ha az előírt felsorolást elvégzi. Legyen A2 egy tagja a H1 csoportnak. Ha A2 felsorolásában nem szerepel minden más versenyző, akkor tehát a nem említettek mind H1-be tartoznak, s ezek összességét H2-vel jelöljük. Mivel A2 ezeket nem említette, mindegyikük megverte A2-t és az A2 által legyőzötteket, ezért a H2 csoport minden tagja megemlíti felsorolásában az A2 által említetteket. Így tovább haladva egyre kevesebb versenyzőből álló H1, H2, ... csoportokhoz jutunk, amíg el nem érünk olyan An versenyzőhöz, akinek felsorolásában minden versenytársa szerepel. Minthogy a csökkenő csoportok sorozata nem lehet végtelen, el kell hogy jussunk ilyen versenyzőhöz.
 

Megjegyzés: A közölt megoldás burkoltan teljes indukcióra épül. Okoskodását a következőképpen is előadhatjuk: Ha csak két résztvevő van, a feladat állítása helyes; tegyük fel, hogy az állítás helyes, ha a résztvevők száma n-nél kevesebb; az n versenyző közül kiválasztott A1 versenyző egy H1 csoportot határoz meg, hacsak maga meg nem felel a követelménynek; H1-ben n-nél kevesebb résztvevő van, az indukciós feltevés szerint van tehát közöttük olyan, akinek felsorolásában H1-nek minden más tagja szerepel, a fentebbiek szerint viszont a H1-be nem tartozók mindegyikét is említi, ez a versenyző tehát megfelel a feladat követelményének.
 

III. megoldás. Az állítást teljes indukcióval bizonyítjuk. Ha csak két résztvevő van, az állítás nyilván helyes. Tegyük fel, hogy helyes az állítás, ha n résztvevő van. Ha tehát n+1 résztvevő van, akkor van az első n között olyan A résztvevő, akinek felsorolásában minden más versenyző szerepel az első n közül. Legyen B az (n+1)-edik résztvevő. Ha B is szerepel A felsorolásában, akkor A megfelel a követelménynek. Ha B nem szerepel A felsorolásában, akkor B le kellett hogy győzze A-t és azokat, akiket A legyőzött; ezért B-nek felsorolásában szerepel A és mindazok, akiket A felsorolt; ekkor tehát B megfelel a követelménynek.
 

IV. megoldás. A versenyzők egy teremben helyezkednek el. Az egyik versenyző kivezeti a teremből azokat, akiket legyőzött (esetleg senkit sem). Ha van még, aki a teremben marad, egyikük újból kivezeti azokat, akiket legyőzött a teremben maradottak közül. Ezt folytatják mindaddig, amíg valaki a termet ki nem üríti. A kiürítő legyőzte azokat, akiket kivezet, és azokat, akik korábban kivezettek, hiszen a teremben maradhatott, ez utóbbiak viszont legyőzték az általuk kivezetetteket. A kiürítő tehát minden társát megemlíti felsorolásában.
 

Megjegyzések: 1. Az első megoldás mutatja, hogy a győztes (vagy a győztesek bármelyike) megfelel a követelménynek. Nem igaz azonban, hogy csak győztes felelhet meg. Sőt még a vesztes is megfelelhet, ezt az alábbi eredménytáblázat példája bizonyítja:
ABCDE|A-1110|B0-101|C00-11|D010-1|E1000-

2. Az is lehetséges, hogy a verseny minden résztvevője megfelel a feladat követelményének. A fenti eredménytáblázat erre is példát nyújt. Mutatja, hogy 5 versenyző esetében ez is lehetséges. Felvetjük a kérdést, hogy hány résztvevős versenyben lehetséges ez.
Ha két résztvevő van, nyilvánvaló, hogy csak egyikük (a győztes) felel meg a követelménynek. Négy résztvevős versenyben sem felelhetnek meg mind a négyen a feladat követelményének. Ha ugyanis van közöttük olyan résztvevő, aki három győzelmet aratott, akkor a többinek felsorolásában ez a versenyző nem szerepel. Ha van olyan résztvevő, akit mindenki legyőzött, akkor ennek felsorolásában senki sem szerepel. Ha viszont mindannyian egy vagy két győzelmet arattak, akkor ketten egyszer-egyszer, ketten pedig kétszer-kétszer győztek, hiszen összesen hat mérkőzés volt; a két egygyőzelmes versenyző egyike legyőzte a másikat, az elsőnek felsorolásában tehát csak két versenytársa (a másik és akit az legyőzött) szerepel.
Bizonyítjuk, hogy ha a résztvevők száma nem 2 vagy 4, akkor lehetséges olyan versenyeredmény, hogy minden versenyző megfelel a feladat követelményének.
Ezt először arra az esetre bizonyítjuk, amikor a versenyzők száma, n páratlan. Állítsuk a versenyzőket egy szabályos n-szög csúcsaiba, arccal a sokszög középpontja felé. Ha mindenki azokat győzte le, akik jobboldalt állnak, akkor mindenki mindenkit felsorol. Ezt könnyű ellenőrizni.
Ha a versenyzők száma páros és 4-nél több, legyen közöttük n férfi és n nő. Ismét egy szabályos 2n-szög csúcsaiba állítjuk őket, váltakozva férfiakat és nőket. Győzze le mindenki a jobbján állókat azzal a kivétellel, hogy a nők jobboldali másodszomszédjuktól vereséget szenvednek. Ilyen versenyeredménynél mindenki felsorolja minden versenytársát függetlenül attól, hogy a sokszög átellenes csúcsaiban állók milyen eredménnyel mérkőznek. Ennek ellenőrzése sem nehéz.
A 7. ábra bemutatja az előírásunk szerinti versenyeredményeket 5 és 6 résztvevő esetében.
 
 
7. ábra
 

Az ábrán a nyíl a győztestől a vesztes felé irányul. A 6 versenyzős esetben az átellenesen állók mérkőzéseinek (elő sem írt) eredményét ábránk nem is jelzi.