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. Tegyük fel, hogy az állítás nem igaz, és tekintsük mindazokat az ellenpéldákat, amelyekben a lehető legkevesebb versenyző szerepel. Ezek mindegyikében keressük ki azt a játékost, (vagy az egyik olyat), aki a lehető legkevesebb döntetlen mérkőzést játszotta, legyen ez . Válasszunk ki olyan ellenpéldát, amelyben döntetlenjeinek száma minimális, jelöljük ezt -val. Megmutatjuk, hogy semmiféle értéket nem vehet fel, ez igazolja az állításunkat. I. Nem lehet . A feltétel szerint mindenkihez található olyan, akivel összesen páratlan sok döntetlent játszott, tehát mindenki legalább egy döntetlen mérkőzést játszott.
1. ábra
II. Nem lehet . Tegyük fel, hogy csak -vel játszott döntetlenül, és hagyjuk el az és játékosokat (1. ábra). Továbbra is ellenpéldát kapunk: a játékosok száma páratlan, és ha a többi résztvevő egy részhalmazában csak játszott volna páratlan sok döntetlent, akkor a halmazhoz nem volna "jó'' résztvevő. Így ellentétbe kerültünk azzal, hogy az ellenpéldában a lehető legkevesebb versenyző szerepel. III. Nem lehet sem. Ha döntetlenül mérkőzött -vel és -vel is, módosítsuk a bajnokság eredményét a következő módon (2. ábra). Ha egy résztvevő -vel döntetlenül játszott, de -vel nem, akkor a -vel való játszmája is legyen döntetlen; ha egy résztvevő -vel és -vel is döntetlenül játszott (mint például ), akkor a és közte lefolyt játszmát nyerje meg . Az összes többi eredményt változatlanul hagyjuk.
2. ábra
Az olvasóra bízzuk annak ellenőrzését, hogy a módosítás után is teljesülnek a feladat feltételei. Ez viszont lehetetlen, hiszen a módosítás után -nak eggyel kevesebb, döntetlenje van, mint előtte, noha feltettük, hogy a döntetlen mérkőzések minimális száma . Mivel több eset nincs, a feladat állítását bizonyítottuk. P. T.
|