Feladat: Gy.2926 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Bakonyi Gábor ,  Bárány Kristóf ,  Fazekas Borbála ,  Katona Zsolt ,  Pap Gyula ,  Végh László ,  Zubcsek Péter Pál 
Füzet: 1995/február, 88 - 90. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorikai leszámolási problémák, Kombinációk, Konstruktív megoldási módszer, Szöveges feladatok, Gyakorlat
Hivatkozás(ok):Feladatok: 1994/szeptember: Gy.2926

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 feladatot általánosabban oldjuk meg: tegyük föl, hogy a csoportok k csapatból állnak, és azok jutnak tovább, akik legfeljebb m vereséget szenvednek. A kérdés pedig az eredeti: hányan juthatnak tovább egy csoportból? Az m≥k-1 esetben persze mindenki továbbjut, így a továbbiakban tegyük föl, hogy m≤k-2 és ennek megfelelően k≥3.
Jelölje a továbbjutók számát t, és vizsgáljuk meg először azokat a mérkőzéseket, amelyeket ők játszottak egymás között. Látható, hogy ez t(t-1)2 mérkőzést jelent: mindenki t-1 másikkal játszott, ez t(t-1), viszont ekkor mindent pontosan kétszer számoltunk. Minden mérkőzésnek volt vesztese, ezért a t továbbjutó csapat összesen legalább t(t-1)2 vereséget szenvedett. Közülük senki sem kapott ki m-nél többször, ezért

t(t-1)2≤tm
teljesül. Ez nyilván fennáll a t=0 esetben, máskor pedig a
t≤2m+1
alakra hozható. Mivel ennek a t=0 is megfelel, így tehát azt kaptuk, hogy a továbbjutók száma legfeljebb 2m+1 lehet.
Hasonló meggondolást alkalmazunk a kiesők egymás közötti mérkőzéseire. Közülük mindegyik csapat legfeljebb t továbbjutótól kaphatott ki, s mivel összesen legalább m+1-szer veszített (hiszen kieső), így legalább m-t+1 kiesőtől is vereséget szenvedett. Azaz a kiesők egymás között összesen legalább (k-t)(m-t+1)-szer veszítettek. Ez nem lehet több, mint az általuk egymással játszott összes mérkőzésük száma, vagyis
(k-t)(k-t-1)2≥(k-t)(m-t+1).
Ez k≠t esetén (ekkor ugyanis k>t, hiszen k≥t nyilvánvaló)
k-t-1≥2m-2t+2,t≥2m-k+3
alakot ölt, s ez tartalmazza a k=t esetet is (k-2≥m alapján).
Azt kaptuk tehát, hogy a lehetséges t számokra
2m-k+3≤t≤2m+1
teljesül. Most megmutatjuk, hogy ezek valóban jók is: minden ilyen t-re megadjuk a mérkőzések olyan kimenetelét, amelynél t csapat jut tovább. Ehhez először kijelölünk t csapatot ‐ ők lesznek a továbbjutók, a többiek kiesnek. A köztük levő mérkőzések eredményét is úgy választjuk meg, hogy mindig a továbbjutó csapat legyen a győztes.
Vizsgáljuk most a továbbjutók egymás közti meccseit. Tekintsük először a t=2m+1 esetet. A csapatokat körbeállítjuk; mindenki legyőzi a tőle jobbra álló m csapatot, a többitől pedig vereséget szenved. Ezzel biztosítottuk, hogy ez a t csapat valóban továbbjut. A t<2m+1 esetekben a következőképpen járunk el: képzeletben 2m+1 csapatra egészítjük ki a továbbjutókat, köztük a már leírt módon elrendezzük az eredményeket, majd a valójában tovább nem jutó csapatok győztes mérkőzéseinek eredményét megfordítjuk. Ez valóban jó, hiszen ekkor a t csapat egyike sem veszített m-nél többször.
Most vizsgáljuk a kiesők mérkőzéseit. Ezúttal a t=2m-k+3 esettel kezdjük. Ekkor k-(2m-k+3)=2k-2m-3 kieső van. Az előbbi ,,körbeállítós'' módszerrel elérhető, hogy a kiesők egyenként k-m-2 meccset veszítenek el egymás ellen. Ezenkívül a továbbjutóktól is kikapnak, tehát összesen k-m-2+2m-k+3=m+1-szer veszítenek, és ezzel kiesnek. A nagyobb t-kre kevesebb kieső lesz, úgyhogy a már látott módon képzeletben kiegészítjük őket 2k-2m-3-ra, beosztjuk a mérkőzéseket, majd a valójában továbbjutók egymás közti eredményeit visszaállítjuk a már rögzítettekre, a kiesőktől elszenvedett vereségeiket pedig győzelemre módosítjuk. Ezáltal a k-t kieső mindegyike legalább m+1-szer veszített, és a továbbjutók korábban már meghatározott eredményei sem változtak.
Figyelmesen megnézve, eddigi gondolatmenetünk kisebb pontosításra szorul. Előfordulhat ugyanis, hogy 2m+1>k vagy 2m-k+3<0 teljesül, és az ilyen t-k nyilván nem lehetségesek. Tehát legfeljebb a
max(0,2m-k+3)≤t≤min(k,2m+1)
állítás lehet igaz. Ekkor viszont a konstrukcióban is gondok lépnek föl: amikor a t továbbjutót 2m+1-re egészítjük ki, talán nincs is annyi csapat, s ugyanez vonatkozhat a kiesők 2k-m-3-ra való kiegészítésre. A következő megfontolással azonban ezek a problémák kiküszöbölhetők.
Ha több csapatra kell kiegészíteni, mint amennyi van, akkor ehhez ,,fiktív'' csapatokat is használunk. Ugyanúgy kiosztjuk a mérkőzések eredményeit, majd először elhagyjuk a fiktív csapatokat (mérkőzéseikkel együtt), utána pedig a többieket (mérkőzéseiket korrigálva). A továbbjutók kiegészítésekor ez a művelet nem növeli a kiválasztott t csapat vereségeinek számát, a kiesőkénél pedig a győzelmekét. Azaz, a továbbjutásra szánt t csapatnak az elhagyás után is legfeljebb m veresége lesz, a k-t másiknak pedig legfeljebb (k-1)-(m-1) győzelme, vagyis az a t csapat továbbjut, a többi pedig nem.
Ezzel tehát minden t-re megadtuk a bajnokság egy megfelelő kimenetelét, ily módon a feladatot megoldottuk. A kérdezett k=5, m=1 és k=6, m=1 esetben a továbbjutók számára
max(0,2-5+3)=0≤t≤3,illetvemax(0,2-6+3)≤t≤3
teljesül, azaz 0, 1, 2 vagy 3 csapat juthat tovább.
 Pap Gyula (Debrecen, Fazekas M. Gimn., II. o.t.) dolgozata alapján

 
Megjegyzés. Sok megoldó csak a továbbjutók maximális számát határozta meg, ezért csak részpontszámot kapott. Nem kapott pontot, aki csak ábrát küldött. Természetesen azok, akik az eredeti feladatot a konkrét esetre (a megadott megoldáshoz hasonló gondolatmenettel) megoldották, 5 pontot kaptak.