Turnausten kombinatoriikka

Abstract

Tutkielmassa käsitellään erilaisia turnauksia ja niihin liittyvää matematiikkaa kombinatoriikan näkökulmasta. Aluksi käydään läpi algebran ja kombinatoriikan aputuloksia, joista tärkeimpiä ovat kongruenssi, kombinatoriset sommitelmat sekä latinalainen neliö. Kongruenssiyhtälön avulla määritellään turnauksia matemaattisesti. Latinalaisten neliöiden avulla voidaan luoda erilaisia turnauksia. Kombinatoriset sommitelmat ovat mukana lähinnä turnausten näkökulmasta, vaikka niillä on paljon muitakin käyttökohteita. Näistä sommitelmista turnauksia koskevat erityisesti (2n, 2, 1)-sommitelmat, kuten seuraavassa nähdään.

Aputulosten jälkeen määritellään kiertoturnaus. Siinä 2n joukkuetta pelaavat vastakkain 2n−1 kierroksella niin, että kaikki pelaavat kaikkia vastaan täsmälleen kerran ja jokainen joukkue kerran kullakin kierroksella. Tällöin pelejä tulee yhteensä n(2n−1). Tämä kiertoturnaus nimenomaan on (2n, 2, 1)-sommitelma. Se pystytään konstruoimaan ainakin kahdella tavalla, joista toinen on kiertomenetelmä ja toinen Kirkmanin konstruointi.

Turnauksessa optimaalisinta olisi pelata vuorotellen koti- ja vieraskentällä. Tästä johtuen joukkueille voidaan määritellä vaihdonrikko. Vaihdonrikko tarkoittaa sitä, että joukkue pelaa kaksi kertaa peräjälkeen kotikentällä tai vieraskentällä. Kaksijakoisessa turnauksessa (joukkueet pelaavat kaksi kertaa muita joukkueita vastaan) 2n joukkueelle vaihdonrikkojen minimimääräksi saadaan todistettua 6n − 6.

Seuraavaksi määritellään seurausvaikutus. Se tarkoittaa, etteivät kaksi joukkuetta tai pelaajaa saa pelata peräkkäin kahta tiettyä muuta joukkuetta tai pelaajaa vastaan. Tällainen turnaus saadaan luotua latinalaisten neliöiden avulla. Kun latinaisen neliön konstruoi tietyllä tavalla, sen avulla saadaan turnaus, jossa ei ole seurausvaikutusta.

Viimeisenä asiana tutkielmassa määritellään Roomin neliö. Siinä esiintyvät peliparit (2n − 1) × (2n − 1)-ruudukossa, joten mukaan tulee myös tyhjiä ruutuja.