Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

6. Bajnokságok 6 csapattal

6. Bajnokságok 6 csapattal

Az alábbi feladatok mindegyikében 6 csapat versenyéről van szó. A megoldásban segíthet, ha lerajzoljuk a B teljes gráfot, melynek csúcsai a csapatoknak, élei a mérkőzéseknek felelnek meg.

11. ábra.

20. feladat Összesen hány mérkőzést játszanak le egy bajnokság során (mindenki mindenkivel pontosan egyszer játszik)? Hány fordulóban bonyolítható le a bajnokság?

Az első kérdésre a válasz: 15. Kis próbálgatással rájöhetünk, hogy ez a 15 mérkőzés lebonyolítható 5 fordulóban.

21. feladat Hányféleképpen párosítható a 6 csapat egy fordulóban, azaz hányféle forduló képzelhető el (nem számít a mérkőzések sorrendje és az se, hogy hol játsszák őket, ki kezd)?

Többféleképpen is okoskodhatunk. Kezdjük például így: rögzítsük a csapatok sorrendjét a sorsolás kedvéért! Az első csapatnak 5 másik közül választhatunk ellenfelet. A sorrendben következő, még ki nem választott csapat ellenfelének kiválasztására már csak 3 lehetőségünk van. Az utolsó mérkőzés ezek után már egyértelműen adódik, tehát 5 · 3 = 15 -féle fordulót lehet szervezni 6 csapat között.

22. feladat Előttünk van egy forduló terve. Hány olyan forduló képzelhető el, amely nem tartalmaz közös mérkőzést az adott fordulóval?

Számoljuk ki azoknak a fordulóknak a számát, amelyeknek van közös mérkőzése az adott fordulóval, majd ezt vonjuk ki a 15-ből! Ha egy forduló nem egyezik meg az adott fordulóval, de van vele közös meccse, akkor egyetlen egy közös meccsük van. Ez a mérkőzés háromféleképpen választható ki az adott fordulóból, a további két mérkőzés kétféleképpen választható, így 15 - ( 1 + 3 · 2 ) = 8 a válasz a kérdésre.

23. feladat Előttünk van két forduló terve. Ha van olyan mérkőzés, amely mindkettőben szerepel, akkor biztos, hogy nem lehet olyan bajnokságot szervezni, amelyben mind a két adott forduló előfordul. Vajon hányféle olyan bajnokság van, amelyben szerepel két előre adott, közös mérkőzés nélküli forduló? (Két bajnokságot ugyanolyannak tekintünk, ha ugyanazokból a fordulókból állnak, a fordulók sorrendje nem számít.)

12. ábra.

Ha a két fordulót együtt rajzoljuk be egy gráfba, akkor minden csúcs foka 2 lesz, így vagy hatszöget (6 hosszú kört) vagy két háromszöget kapunk. Háromszög mégsem jöhet szóba, mert három oldaléléből csak egy-egy tartozhat egy-egy fordulóhoz. Tehát a két forduló együtt szükségképpen hatszög, amelyet a csúcsok átbetűzésével, átrendezésével az ábrán látható formára rendezhetünk át. Tervezzünk tovább! Nézzük meg, hogy a B 1 B 3 mérkőzés B 2 melyik mérkőzésével lesz egy fordulóban! Nem lehet a B 2 B 6 meccsel, mert akkor B 4 B 5 maradna ebben a fordulóban, de az a mérkőzés már be van osztva. Ugyanígy nem jön szóba a B 2 B 4 mérkőzés se, csak B 2 B 5 marad, a forduló harmadik mérkőzése pedig B 4 B 6 lesz. Hasonló lépésekkel kapjuk az egyetlen lehetőséget a két további fordulóra is: B 2 B 6 , B 1 B 4 , B 3 B 5 , illetve B 2 B 4 , B 3 B 6 , B 1 B 5 . Tehát mindig egyetlen megfelelő bajnokság van.

24. feladat Képzeljük el az összes lehetséges bajnokságot! Közülük hányban szerepel egy adott forduló?

Használjuk fel az előző két feladat eredményét! Az adott forduló és tetszőleges, vele közös mérkőzést nem tartalmazó forduló meghatároz egy bajnokságot. Ebben a bajnokságban még 3 további olyan forduló van, amely nem tartalmaz az eredeti fordulóval közös mérkőzést. A 8 ilyen fordulóból még négy marad, ezek az eredeti fordulóval még egy bajnokságot tesznek ki. Tehát minden forduló 2 bajnokságban szerepel.

25. feladat Összesen hány különböző bajnokság van?

6, hiszen a 15 forduló mindegyike 2 bajnokságban szerepel, 15 · 2 = 30 , de ebben minden bajnokságot ötször, minden fordulója szerint egyszer-egyszer számoltunk.

26. feladat Adott két (különböző) bajnokság. Hány közös forduló van bennük?

Bármelyik két bajnokságban legfeljebb egy közös forduló van, hiszen két forduló már meghatározza a bajnokságot (lásd a 22. feladatot). Az előző feladat eredménye szerint a 15 forduló mindegyikéhez található két olyan bajnokság, amelynek az a forduló közös tagja. Mivel a 6 bajnokságból épp 6 2 = 15 -féleképpen választható ki kettő, így bármelyik kettőben pontosan egy közös forduló van.

A feladatok megoldásából az derült ki, hogy 6 csapatnak épp 6-féleképpen szervezhető bajnokság, összesen 15 elképzelhető forduló van, mindegyikhez pontosan egy olyan bajnokság-pár van, amelynek közös fordulója az adott forduló. Ez azt jelenti, hogy a 6 bajnokság megfeleltethető egy A teljes gráf 6 csúcsának, és a 15 forduló megfeleltethető ugyanezen gráf 15 élének úgy, hogy két csúcs közti él megfelel a csúcsokhoz tartozó bajnokságok közös fordulójának. Ebben a megfeleltetésben két él pontosan akkor találkozik egy közös csúcsban, ha benne vannak egy bajnokságban, tehát ha nincs bennük közös mérkőzés. Az egy csúcsból kiinduló 5 él egy bajnokság 5 fordulója.

13. ábra.

Az előző fejezet utolsó része alapján a 6 különböző bajnokságot a 6 A i szimbólumnak, a 15 fordulót a 15 A i A j párnak feleltetjük meg, tehát ezeket írhatjuk az A „bajnokság-gráf” csúcsaira, illetve éleire. Ez a csoda! Pontosan annyi bajnokság, illetve forduló van, ahány csapat, illetve ahány lehetséges mérkőzés. Ráadásul a fordulók és bajnokságok rendszere épp olyan, amilyet szerettünk volna. Ez a 6-os szám különlegessége.

Vizsgáljuk most meg a kimaradt (4) feltételt, azaz nézzük meg, hogy van-e háromszög vagy négyszög 36 csúcsú G gráfunkban! Tegyük fel először, hogy az ( A 1 , B 1 ) , ( A 2 , B 2 ) , ( A 3 , B 3 ) csúcsok háromszöget alkotnak G -ben. Ez azt jelenti, hogy az A 1 A 2 fordulóban B 1 B 2 -vel játszik, míg az A 2 A 3 fordulóban van a B 2 B 3 , az A 3 A 1 fordulóban pedig a B 3 B 1 mérkőzés. Az A gráfban az A 1 A 2 , A 2 A 3 , A 3 A 1 élek háromszöget alkotnak, csakúgy mint a B gráfban a B 1 B 2 , B 2 B 3 , B 3 B 1 mérkőzéseknek megfelelő élek. A 19. feladat megoldása során szerzett tapasztalatok segítségével könnyen bizonyíthatjuk, hogy ez nem lehetséges. Valóban, az A 1 A 2 , A 2 A 3 fordulók közös csúcsból indulnak ki, tehát a nekik megfelelő fordulók közös mérkőzés nélküliek (az A 2 csúcshoz tartozó bajnokságban vannak), így a két forduló hat mérkőzése a B gráfban egy hatszöget alkot. Az A 3 A 1 él az A gráfban az egyetlen olyan él, amelynek A 1 A 2 -vel és A 2 A 3 -mal is van közös csúcsa, de az nem A 1 A 2 és A 2 A 3 közös csúcsa. A 3 A 1 tehát B -ben az egyetlen olyan fordulónak felel meg, amely A 1 A 2 fordulójával is hatszöget alkot, A 2 A 3 fordulójával is hatszöget alkot, de nincs benne az A 1 A 2 és A 2 A 3 által egyértelműen meghatározott bajnokságban. Így az A 1 A 2 , A 2 A 3 , A 3 A 1 fordulók egyértelműen berajzolhatók a B gráfba, minden esetben az ábrára rajzolt gráfot kapjuk, csak az indexek elrendezése lehet más. Látható, hogy ebben a gráfban egyáltalán nincs háromszög.

14. ábra.

Tegyük most fel, hogy ( A 1 , B 1 ) , ( A 2 , B 2 ) , ( A 3 , B 3 ) , ( A 4 , B 4 ) négy hosszúságú kör csúcsai G -ben. Ekkor az A i -k is a B i -k is különbözők kell legyenek, hiszen például B 2 = B 4 esetén a ( B 1 , B 2 ) ( B -beli) él benne lenne az ( A 1 A 2 ) és ( A 1 A 4 ) ( A -beli) élekhez rendelt fordulókban, pedig azokban nincs közös mérkőzés (hiszen kiegészíthetők az A 1 -nek megfelelő bajnokságra). Vizsgáljuk meg, hogy nézhetnek ki az A 1 A 2 , A 2 A 3 , A 3 A 4 és A 4 A 1 élekhez tartozó fordulók B -ben. Az előző bekezdéshez hasonlóan az A 1 A 2 , A 2 A 3 élek együtt egy hat hosszúságú kört alkotnak. Az A 3 A 4 forduló B -beli élei is hatszöget alkotnak az A 2 A 3 -nak megfelelő élekkel, A 1 A 2 éleivel azonban nem. A 3 A 4 és A 1 A 2 nincsenek benne egy bajnokságban, hanem van bennük egy közös mérkőzés, azaz egy közös B -beli él. Így az első három fordulónak megfelelő élek lényegében egyféleképpen nézhetnek ki.

15. ábra.

Most már könnyű látni, hogy ahhoz, hogy A 4 A 1 élei hatszöggé egészítsék ki A 3 A 4 és A 1 A 2 éleit, de pontosan egy él legyen közös A 4 A 1 -ben és A 2 A 3 -ban, lényegében csak egyféleképpen húzhatjuk be A 4 A 1 éleit. Jól látható, hogy az ábrán nincs olyan B 1 B 2 B 3 B 4 négyszög, amelynek élei sorban az A 1 A 2 , A 2 A 3 , A 3 A 4 , A 4 A 1 fordulókhoz tartoznak.