Kombinatorika: példa "mérkőzéses" feladatra

Egy labdarúgó tornán összesen 66 mérkőzést játszottak, egy kosárlabda tornán összesen 132 mérkőzést játszottak, és még sorolhatnánk tovább a példákat… Nagyon sok hasonló jellegű, kombinatorikával kapcsolatos példa kezdődik így a tankönyvekben, az interneten fellelhető feladatokban. Az esetek többségében csak a példák “körítése” más, a megoldást hasonló módszerrel kaphatjuk meg. Általában arra kérdeznek rá a feladatokban, hogy hány csapat indult a tornán, ha tudjuk a mérkőzések számát, milyen sorrendben végezhettek a csapatok, ha nem volt holtverseny, vagy ha holtversenyben végzett az első helyen két csapat, stb. Ezek a feladatok tökéletesen megfelelnek arra, hogy a kombinatorika alapjait megértsük, begyakoroljuk és egy hétköznapi, valós példán keresztül tanuljuk meg az alkalmazandó szabályokat, képleteket.

Álljon itt példaként a következő feladat:

Egy labdarúgó tornán összesen 182 mérkőzést játszottak rövid, 10 perces meccseken. Hány csapat vett részt a tornán, ha mindenki mindenkivel kétszer játszott?

Első ránézésre azt gondolhatjuk, nem sok információt kaptunk a feladat megoldásához, de érdemes végig gondolni, mi az, amit tudunk:

Mivel nem tudjuk, hány csapat játszott, jelöljük n-nel a csapatok számát!
Ha mindenki kétszer játszott egymással, feltételezhetjük, hogy két körben zajlottak a mérkőzések.
Mivel mindenki mindenkivel játszott, ezért azt is tudjuk, hogy egy adott csapat $(n-1)$ csapattal játszott egy körben (saját magán kívül mindenki mással játszott, tehát az összes (n) csapatból kivonunk egyet).
N db csapat van, ezért összesen $n(n-1)$ mérkőzést játszottak le egy körben (minden csapat (n-1) mérkőzést játszott). Ezt a számot azonban le kell osztanunk kettővel, mivel ebben a számításban az is megjelenik ugyanúgy, ha A csapat játszik B csapattal, de az is, ha B csapat játszik A csapattal, ez a kettő pedig ugyanaz a mérkőzés. Tehát egy körben $\frac{n(n-1)}{2}$ db mérkőzést játszanak le.
Mivel két körben zajlottak a megmérettetések, ezért összesen a meccsek száma:
$\frac{n(n-1)}{2}+\frac{n(n-1)}{2}=n(n-1)$

Innentől kezdve könnyű dolgunk van, ugyanis fel tudunk írni egy egyszerű egyenletet:

$n(n-1)=182$

Vegyük észre, hogy egy másodfokú egyenletet fogunk kapni:
$n^2-n=182$

$n^2-n-182=0$

Az egyenlet megoldásai pedig a következők lesznek: $n_{{1}}=14$ és $n_{{2}}=-13$ . Ebből látható, hogy helyes megoldás egyedül a 14. Tehát a labdarúgó tornán összesen 14 csapat szerepelt.

Kérdésként még felmerülhet az is például, hogy hányféle sorrendben végezhetnek a csapatok, ha nem volt holtverseny. Ez a feladat is egyszerűen megoldható az ismétlés nélküli permutáció alkalmazásával. Ez a fogalom azt jelenti, hogy néhány különböző (ezt jelenti az ismétlés nélküli) dolgot sorba rendezünk.

$P_{{n}}=n!=n\cdot(n-1)\cdot(n-2)\cdot...\cdot2\cdot1$

Az első helyen 12 csapat végezhet, míg a második helyen már csak 11 csapat (az első helyen már van egy csapat), a harmadik helyen 10 (az első két helyen már van egy-egy csapat), és így tovább, és így tovább… A megoldás:

$12\cdot11\cdot10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1=12!=479001600$

Tehát a labdarúgó tornán összesen 479001600-féle sorrendben végezhetnek a csapatok.

Ennek a feladatnak a megoldásából is látszik, hogy egy-egy példát könnyedén meg tudunk oldani akkor is, ha kevés adatunk van vagy ha elsőre nehéznek is tűnik. Csak végig kell gondolnunk, milyen információk állnak rendelkezésünkre.

Átfogó összefoglalás kombinatorika témakörben a következő linken található: https://hu.wikipedia.org/wiki/Kombinatorika

Kérdés esetén keressetek bátran valamelyik elérhetőségünkön!