"Végy egy magyart!"

Játékos feladatok, ravasz rejtvények megoldása, gyakorisági becslések közben alakult ki a kombinatorika. Az utóbbi évtizedekben azonban kiderült, hogy a számítógép-tudomány és az informatika egyik alappillére. Az ezzel együtt járó ugrásszerű fejlődésében a magyar matematikusok hozzájárulása világszerte elismert. Az Élet és tudomány interjúja Katona Gyula matematikussal.

A kombinatorika szót hallva mindenkinek támadnak képzetei: sorrendek, kiválasztások, csoportosítások...

Gondolom, a leszámláló kombinatorikából fogunk kiindulni. Egy feladatot mindenki meg tud oldani: kiszámítani egy körmérkőzés játszmáinak számát: mondjuk 10 sakkozó mindegyike játszik az összes többivel, ami 10×9 irányított kapcsolat, A-B és B-A két mérkőzés. De ha nincs visszavágó, minden pár csak egy mérkőzést játszik, osztani kell 2-vel: a játszmák száma ilyenkor 45.
- Hogy ki játszik a fehérrel, majd eldöntik valami módon. Elemezzük tovább ezt a sporteseményt. Ha azt szeretnénk, hogy mindenki minden nap legfeljebb csak egy mérkőzést játsszon, miként lehet a legrövidebb idő alatt lebonyolítani ezt a versenyt?

Nyilván úgy, ha minden nap mindenki játszik valakivel, azaz "erőnyerők" soha sincsenek. Esetünkben naponta asztalhoz ülhet 5 pár, és kilenc nap alatt lefolytatható a verseny.
- De vajon lebonyolítható-e ez a gazdaságos program? Mondjuk a szervező a következő szabály szerint akar eljárni. Mikor a versenyzők a reggelinél egy kerek asztal körül ülnek sorszámozott székeiken, úgy jelöli ki az aznapi mérkőzéseket, hogy az 1-től indulva párosít mindenkit a tőle balra ülő első olyannal, akivel még nem játszott (és akinek még nincs aznapra ellenfele). Amint az 1. ábrán vázoltuk, ez a logikusnak látszó szabály már a második napon csődöt mond, mert utolsónak a 9. és 10. versenyző marad, és ők már lejátszottak. A forduló csak úgy tehető teljessé, ha átrendezzük kissé a párokat. És azután hogyan lesz tovább? Olvasóink próbálják "megszervezni" ezt a 10-es körmérkőzést, és tapasztalni fogják, hogy nem is olyan egyszerű.

Tellér Mária rajza

Ne lapozzanak túl gyorsan, mert a következő oldalon ott a megoldás.

Ez a szervezési probléma tovább is bonyolítható.
- Növelhetjük a játék résztvevőinek számát. Az ultit hárman játsszák. Ha egy klubban 6 ember közül ki kell választani a legjobb ultizót, az úgy történhet igazságosan, ha mindenki kipróbálja a tudását az összes lehetséges két ellenféllel. Más szóval, a játékosok az összes hármas csoportosításban játszanak egy partit, és akinek az összesített nyereménye a legtöbb, azt tekinthetik a legjobbnak. A 6 emberből pontosan 20 hármas alakítható, egyidejűleg két parti folyhat; ez a válogató legalább 10 fordulót igényel, de annyiban le is bonyolítható.
Az egyik asztalhoz leültetjük az egyik játékost, Aladárt, és mellé az összes lehetséges párt a többi 5-ből - ami 5×4/2 = 10-féleképp lehetséges; a másik asztalhoz ül a maradék 3 ember.

Az egyik asztaltársaság egyértelműen meghatározza a másikat.
- De mi lesz 9 ember esetén?

Annyit mindenképp mondhatunk, hogy Aladárnak ekkor 8×7/2 = 28 párral kell játszania, és másik két asztalnál a többi két hármasnak.
- Már korántsem olyan világos, hogy másik két asztalnál hogy kell leültetni a maradék 6 embert úgy, hogy minden alkalommal olyan csoportosításban legyenek, amilyenben eddig még nem voltak, és hogy ez megvalósítható-e. Rohamosan növekszik a mérkőzésszám. Az összes lehetséges hármast most 84-féleképp lehet összeállítani. És miként kellene megszervezni 30 játékos válogatóját?

Csak széljegyzetként teszem hozzá, hogy minden csoport kétféle sorrendben ülheti körül az asztalt, és a játékban nem közömbös, hogy ki után következünk.
- És az sem, hogy ki kezd, de ne a válogatás módszerére figyeljünk, hanem a csoportok szervezésére. Ez a matematikai kérdés. Meg tudjuk-e szervezni 3-mal osztható számú emberből a körmérkőzést teljes fordulókban. Vagy ha 50 emberből ötszemélyes csapatokat alakítunk - legyen már mellékes a játék mikéntje -, megszervezhető-e, hogy egyidejűleg mindenki játszik, és minden 5-ös összeállítás pontosan egyszer szerepel. Sylvester angol matematikus úgy vélte, hogy ha a játékban szereplők számával osztható az összes résztvevők száma, akkor ez mindig megvalósítható. Sejtését 1850-ben mondta ki, és 1975-ig kellett várni, míg a problémára Baranyai Zsolt (28 éves korában) megoldást adott.

Herczeg János