!Algoritmi täyskierrosturnauksen paritukseen

Ihanteellisessa yksinkertaisessa täyskierrosturnauksessa seuraavat ehdot toteutuvat:

*jokainen pelaa jokaista vastaan, mutta vain kerran
*jokainen pelaa yhtä monta tai melkein yhtä monta peliä mustilla ja valkeilla
*pelattu väri vaihtuu joka kierroksella
*jokainen pelaa joka kierroksella, ts. vapaakierroksia ei ole

Nämä kaikki eivät voi toteutua täydellisesti yhtä aikaa ei-triviaalissa tapauksessa. Todistus jää harjoitustehtäväksi ahkerille lukijoille.

Esitetään algoritmi parituksen muodostamiseen, joka takaa parituksen, joka on melkein yo. ehtojen mukainen.

Olkoon pelaajia parillinen määrä. Heihin viitataan jatkossa numeroilla 1,...,n, missä n on parillinen. Koska jokainen pelaa pelin kaikkia paitsi itseään vastaan, on tällöin turnauksessa vähintään n-1 kierrosta. Jos jokaiselle kierrokselle jokaiselle pelaajalle löytyy sopiva vastustaja, riittää n-1 kierrosta, eikä useampia tarvita.

Kuvataan kierrosta ja sen paritusta (n/2)x2-matriisilla, jonka alkioina ovat pelaajia vastaavat luvut. Samalla sarakkeella olevat pelaajat pelaavat pelin keskenään. Olkoon ensimmäisen kierroksen paritus seuraava:

|1 | 2 | 3| ...| n/2
|n | n-1| n-2 |... |n/2+1

Valitaan lisäksi peleissä värit siten, että ylärivissä parittomilla luvuilla pelaavilla on mustat ja parillisilla valkeat.

Kaikki muiden kierrosten k, k=2,3,...,n-1, saadaan induktiivisesti edellisen kierroksen parituksesta seuraavalla tavalla:

Matriisissa (1,1)-alkio, eli pelaaja 1, säilyy aina samana. Muita kierretään yksi askel myötäpäivään sillä tavalla, että ylärivillä jokainen alkio siirtyy yhden paikan oikealla, paitsi rivin viimeinen, joka siirtyy alemman rivin oikeanpuoleisimmaksi alkioksi. Alarivin alkioita siirretään yksi askel vasemmalla, paitsi vasemmanpuoleisinta alkiota, joka siirretään pelaajan 1 oikealle puolelle. Siis vain pelaajan 1 suhteellinen asema muihin pelaajin nähden muuttuu, koska hän on ainoa joka pysyy paikallaan.

Pelaaja 1 pelaa mustilla parittomilla kierroksilla ja valkeilla parillisilla kierroksilla. Muissa pareissa pelataan aina samoilla väreillä kuin samassa paikassa pelattiin ensimmäisellä kierroksella.

Menetelmä päättyy kun on paritettu n-1 kierrosta.

Jos pelaajia on pariton määrä, kutsutaan mukaan Byen veljeksistä vanhin, joka senioriteettinsä nojalla pelaa pelaajana yksi. Peli häntä vastaan tulkitaan vapaakierrokseksi.

Esimerkki. Olkoon paritettavana kuuden pelaajan täyskierrosturnaus. Esitetään seuraavassa matriisit kierroksille 1-5, missä lihavoidut numerot tarkoittavat mustalla pelaamista:

Kierros 1
|__1__ |2 |__3__
|6 |__5__ |4

Kierros 2
|1 |6 |__2__
|__5__ |__4__ |3

Kierros 3
|__1__ |5 |__6__
|4 |__3__ |2

Kierros 4
|1 |4 |__5__
|__3__ |__2__ |6

Kierros 5
|__1__ |3 |__4__
|2 |__6__ |5

!Perustelu menetelmän toimivuudelle

Selvästi jokaisella pelaajalla on vastus joka kierroksella. Todetaan siis, että yksikään pelaaja ei pelaa kahdesti samaa vastustajaa vastaan, sekä että värit jakautuvat niin, että kaikilla pelaajilla heidän mustilla ja valkeilla pelattujen peliensä erotuksen itseisarvo on 1. Tämä on parittomalla pelimäärällä parhain mahdollinen tulos.

__Väite__: Jokainen pelaaja pelaa jokaista vastaan kerran.

__Todistus__:  Riittää osoittaa, että yksikään pelaaja ei pelaa kahdesti samaa pelaajaa vastaan. Tällöin väite seuraa kierrosten määrästä. Selvästi pelaaja 1 pelaa joka pelin eri vastustajaa vastaan.

__Vastaoletus__: eri pelaajat a ja b pelaavat kaksi peliä keskenään.

Jos näin tapahtuu, voidaan olettaa yleisesti, että ensimmäinen heidän keskeisistään peleistä tapahtuu niin, että pelaaja a on matriisin ylärivillä ja b vastaavalla sarakkeella alarivillä. Tällöin pelaajan a ja b välillä on parillinen määrä muita pelaajia, jotka on paritettu keskenään, kulkien matriisin yläriviä oikealla ja jatkaen alariviä vasemmalle oikeasta laidasta. Seuraavalla kierroksella a siirtyy oikealle matriisissa ja b vasemmalle, joten seuraavan kerran heidän kohdatessaan täytyy pelaajan b olla ylärivillä ja pelaajan a alarivillä. Nyt kuitenkin paritusten muodostussäännön nojalla pelaajien a ja b välillä (nyt matriisin vasemmalta puolelta lukien) ovat samat pelaajat, sekä vasemmalla oleva pelaaja 1. Koska tämä on pariton määrä, on mahdotonta, että pelaajat a ja b ovat samalla sarakkeella.

Lisäksi menettely loppuu n-1:n kierroksen jälkeen, joten  toista mahdollisuutta alkukierroksen parituksen syntymiseen ei ole. Näin ollen vastaoletus on väärä ja väite on tosi. MOT

__Väite__: jokainen pelaa melkein yhtä monta peliä valkeilla ja mustilla (erotuksen itseisarvo 1)

__Todistus__: Pelaaja 1 pelaa joka toisen pelin mustilla ja joka toisen valkeille. Hän aloittaa mustilla, joten selvästi hän tulee pelaaman yhden pelin enemmän mustilla kuin valkeilla. Muut pelaajat pelaavat kerran jokaisella paikalla paitsi (1,1)-alkion kohdalla. Muissa paikoissa kuin pelaajaa 1 vastaan pelaamisväri ei muutu eri kierroksilla, joten he pelaavat näissä paikoissa yhteensä yhtä monta peliä valkeilla ja mustilla. Pelaajaa yksi vastaan pelattu väri määrää kumpaa väriä he pelaavat yhden pelin enemmän. MOT

Menetelmää voidaan soveltaa yhden illan pikapeliturnauksissa ihan lennossa, jos jokainen vain muistaa edellisen kierroksen istumapaikkansa ja kierroksen numeron. Muuten menetelmän avulla voidaan määrätä paritus ja pelattava väri jokaiselle kierroksella ja sitten arpoa kuka osallistujista pelaa milläkin luvulla.

----

Kommentit ovat tervetulleita. Kirjoita alle nimesi jos kommentoit asiaa laajemmin. Sivun voisi linkittää muualtakin kun Oulun turnaussivulta, jos se ansaitsee pysyvän elämän wikissä.

(pikkuedittejä: luku vai numero? kuka sen tietää...)

[Pekka Karjalainen|PekkaKarjalainen], 24.10.2004