Feladat: Gy.2193 Korcsoport: 16-17 Nehézségi fok: nehéz
Füzet: 1985/február, 64 - 65. oldal  PDF  |  MathML 
Témakör(ök): Diofantikus egyenletek, Egészrész, törtrész függvények, Kombinációk, Szöveges feladatok, Gyakorlat
Hivatkozás(ok):Feladatok: 1984/április: Gy.2193

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.

Tekintsük az általános esetet: legyen a résztvevők száma n, a bajnok pedig nyerjen k mérkőzést. Az élen nem volt holtverseny, így a többiek mindegyike legfeljebb (k-1)-szer győzött. A mérkőzések száma tehát ‐ a nyertesek szempontjából összeszámolva ‐ legfeljebb k+(n-1)(k-1). Egy n résztvevős körmérkőzéses bajnokságon, ahol mindenki játszik mindenkivel, a mérkőzések száma n(n-1)2. Ez azt jelenti, hogy

n(n-1)2≦k+(n-1)(k-1),ahonnan(1)n+12-1n≤k.(2)


A legkisebb k egész szám, melyre (2) teljesül, [n2]+1, így a bajnoknak legalább [n2]+1 mérkőzést kell nyernie. Ez elő is fordulhat például az alábbi módon: Álljanak körbe a résztvevők, és sorban minden versenyző verje meg a tőle balra álló [n2] db versenyzőt, ha az még nem verte meg őt. Így mindenki mindenkivel játszik, minden versenyző legfeljebb [n2] mérkőzést nyer meg, és van olyan ‐ például az, akihez először rendeltük hozzá az általa legyőzött játékosokat ‐, aki éppen annyit. Egy ilyen játékos valamelyik elvesztett mérkőzését változtassuk megnyertté. Így ő a bajnok [n2]+1 győzelemmel.
A fenti gondolatmenet szerint n=10 és n=11 esetén is legalább 6 mérkőzést nyert meg a verseny győztese, és létezik is olyan kimenetele a versenynek, amikor ennyi győzelem elegendő az első helyhez.
 

Megjegyzések. 1. Sokan nem bizonyították, hogy lehetséges a bajnokságnak olyan kimenetele, hogy valaki 6 megnyert mérkőzéssel győz, azaz hogy a bajnok győzelmeinek számára adott alsó becslés éles.
2. Látható, hogy ha az élen holtversenyt is megengedünk, akkor 5 győzelem már elegendő lehet a bajnokság megnyeréséhez.