Feladat: 1.22.
* Egy sakkedzésen minden játékos legfeljebb
k pontot szerzett (döntetlenért fél pont, győzelemért egy pont jár). Bizonyítsuk be, hogy akkor
a) van olyan játékos, aki legfeljebb
2k mérkőzést játszott;
b) a játékosok elhelyezhetők
2k+1 teremben úgy, hogy az azonos terembe kerülő játékosok még nem játszottak egymással. (Arany Dániel-verseny, 1990H)
Megoldás: 1.22
a) Ha
n versenyző volt és mindenki legfeljebb
k pontot szerzett, akkor az összesen megszerzett pontszám legfeljebb
nk. Ez ugyanennyi mérkőzést jelent. Tehát összesen legfeljebb
nk mérkőzés zajlott már le. De ha mindenki legalább
2k+1 mérkőzést játszott volna, akkor ez összesen legalább
n(2k+1)/2 mérkőzést jelentene, ami több, mint
nk.
b) A részvevők számára vonatkozó teljes indukcióval bizonyítunk. Ha
n<2k+2, akkor az állítás triviális, így kezdő lépésünk van.
Tegyük fel, hogy
n-1 versenyző esetén az állítást már tudjuk. Ha
n versenyzőnk van, akkor is tudjuk a) szerint, hogy van egy
V versenyző, aki legfeljebb
2k mérkőzést játszott. Osszuk be tehát a többi
n-1 versenyzőt
2k+1 terembe a megfelelő módon. Ezt az indukciós feltétel szerint meg tudjuk tenni, hiszen ha csak erre az
n-1 versenyzőre szorítkozunk, akkor is igaz, hogy a közöttük lezajlott mérkőzéseket nézve is mindenki legfeljebb
k pontot szerzett.
Nézzük, hány teremben lehet olyan versenyző, akivel
V már játszott. Mivel ő legfeljebb
2k versenyzővel játszott, legfeljebb
2k ilyen terem van. Van tehát olyan terem, amelybe be tudjuk tenni. Ezt akartuk bizonyítani.