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 . Válasszuk ki a legtöbb győzelmet szerzett versenyzőt (ha több ilyen is van, ezek egyikét), jelöljük őt -val, győzelmeinek számát pedig -val. Ha , akkor mindenkit legyőzött, tehát díjazott. Ha , akkor van legalább egy olyan versenyző, aki -t legyőzte. Tegyük fel, hogy nem kapott díjat, azaz van olyan versenyző, aki -t megverte, és nem kapott ki egy olyan versenyzőtől sem, akit legyőzött. Ekkor azonban megverte az összes, -tól vereséget szenvedett versenyzőt és -t is, azaz legalább győzelme van, ami ellentmond annak, hogy győzelmeinek száma maximális. Tehát díjazott. Térjünk rá a feladat állításának igazolására. Tegyük fel, hogy egyedül kapott díjat, ugyanakkor nem győzött le mindenkit. Legyen , , , az összes olyan versenyző, akit legyőzött, a többi (, , , ) versenyző pedig megverte -t. Mivel díjazott, azért az összes versenyző kikapott legalább egy -től. Tekintsük a 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 -t vagy megverte, vagy egy legyőzőjét megverte. Jelöljük őt -gyel. (mint ahogy az összes ) megverte -t, és megverte az összes egy legyőzőjét, nevezetesen -t. Ez azt jelenti, hogy a teljes bajnokságban is díjat kapott, ez pedig ellentmond annak, hogy az egyedüli díjazott. Tehát a versenyzők halmaza üres, az valóban legyőzött mindenkit. |