Turnausten kombinatoriikka
Kuosa, Juha (2019-04-10)
Turnausten kombinatoriikka
Kuosa, Juha
(10.04.2019)
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
avoin
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2019041212168
https://urn.fi/URN:NBN:fi-fe2019041212168
Tiivistelmä
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.
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.