Feladat: F.3251 Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 1999/október, 413 - 414. oldal  PDF  |  MathML 
Témakör(ök): Logikai feladatok, Feladat
Hivatkozás(ok):Feladatok: 1998/november: F.3251

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.

Először megmutatjuk, hogy legalább egy versenyző kapott díjat. Legyen a versenyzők száma n. Válasszuk ki a legtöbb győzelmet szerzett versenyzőt (ha több ilyen is van, ezek egyikét), jelöljük őt A-val, győzelmeinek számát pedig k-val. Ha k=n-1, akkor A mindenkit legyőzött, tehát díjazott. Ha k<n-1, akkor van legalább egy olyan versenyző, aki A-t legyőzte. Tegyük fel, hogy A nem kapott díjat, azaz van olyan C versenyző, aki A-t megverte, és nem kapott ki egy olyan versenyzőtől sem, akit A legyőzött. Ekkor azonban C megverte az összes, A-tól vereséget szenvedett versenyzőt és A-t is, azaz legalább k+1 győzelme van, ami ellentmond annak, hogy A győzelmeinek száma maximális. Tehát A díjazott.
Térjünk rá a feladat állításának igazolására. Tegyük fel, hogy egyedül A kapott díjat, ugyanakkor nem győzött le mindenkit. Legyen B1, B2, ..., Bk az összes olyan versenyző, akit A legyőzött, a többi (C1, C2, ..., Cn-k) versenyző pedig megverte A-t. Mivel A díjazott, azért az összes C versenyző kikapott legalább egy B-től.
Tekintsük a C versenyzők egymás közötti mérkőzéseit. A már bizonyítottak szerint ebben a ,,minibajnokságban'' van díjazott, azaz olyan, aki az összes többi C-t vagy megverte, vagy egy legyőzőjét megverte. Jelöljük őt C1-gyel.
C1 (mint ahogy az összes C) megverte A-t, és megverte az összes B egy legyőzőjét, nevezetesen A-t. Ez azt jelenti, hogy C1 a teljes bajnokságban is díjat kapott, ez pedig ellentmond annak, hogy A az egyedüli díjazott. Tehát a C versenyzők halmaza üres, az A valóban legyőzött mindenkit.