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 feladat állítását teljes indukcióval bizonyítjuk. Ha , akkor összesen 2 játékos van, ezek egy mérkőzést játszanak. A győztes lesz , a vesztes , és a feladat állítása nyilván teljesül. Tegyük fel ezután, hogy az állítás -re igaz, és hogy versenyző játszik körmérkőzést. Azt kell belátnunk, hogy van versenyző, , , , , akik közül akkor és csak akkor győzte le -t, ha . Legyen egy tetszőleges játékos. a körmérkőzés során ellenféllel játszott. Ezek között lesz , akikkel szemben ugyanazt az eredményt éri el (vagy mindegyiket legyőzi, vagy mindegyiktől kikap). Ellenkező esetben ugyanis legföljebb ellenfelét győzhetné le és legföljebb ellenfelétől kaphatna ki, de ez összesen legfeljebb: ellenfél volna. Ez a játékos (akivel szemben ugyanolyan eredményt ért el), szintén teljes körmérkőzést játszott, így az indukciós feltevésünk szerint van köztük , , , akik közül , pontosan akkor győzte le -t, ha . Most vagy mindegyik ,-t legyőzte, vagy mindegyiktől kikapott. Az első esetben legyen , , , , , a második esetben legyen , , , . A -k ilyen választása mellett pontosan akkor győzte le -t, ha . Mindenképp találtunk tehát versenyzőt a kívánt tulajdonsággal. Ezzel a teljes indukciós lépést és a feladat állítását bebizonyítottuk. Megjegyzés. Erősebb módszerekkel bizonyítható, hogy játékos körmérkőzése után versenyzőt már nem feltétlenül lehet találni a kívánt tulajdonsággal. Feltehető a következő kérdés: mekkora az a legnagyobb szám, amelyre igaz, hogy játékos körmérkőzése után feltétlenül van versenyző, , , , akik közül pontosan akkor győzte le -t, ha ? A feladat azt állítja, hogy , másrészt ‐ mint említettük ‐ . Nem ismeretes azonban, hogy az és a között pontosan hol helyezkedik el.
|