Suuren salin pyöreän pöydän ympärillä oli 24 tasaisin välimatkoin aseteltua nimettyä paikkaa. Kun pyöreän pöydän ritarit saapuivat saliin, oli valitettavasti pimeää, ja kaikki ritarit istuivat vahingossa väärille paikoille. Osoita, että pöytää kiertämällä saadaan ainakin kahden ritarin nimilaput oikeille paikoille.
Tässä ongelmassa vaikuttaa yksinkertaisuudestaan huolimatta sangen vahva matemaattinen periaate, jota kutsutaan kyyhkyslakkaperiaatteeksi. Toisinaan sitä kutsutaan myös kehittäjänsä Johann Peter Gustav Lejeune Dirichlet’n (1805–1859) mukaan, mutta pitäytykäämme tässä hieman hauskemmassa – ja silti yleisesti tunnetussa – nimityksessä. Kyyhkyslakkaperiaatteessa on kyse siitä, että jos 
asiaa pitää laittaa 
laatikkoon ja 
, niin ainakin yhteen laatikkoon tulee ainakin kaksi asiaa.
Kuinka pyöreän pöydän ritarit sitten liittyvät kyyhkyslakkaperiaatteeseen? Yleisyydestä luopumatta voidaan sopia, että pöytää kierretään esimerkiksi vastapäivään. Nyt kukaan ritareista ei ole omalla paikallaan, joten jokainen on korkeintaan 23 paikan päässä omasta nimilapustaan. Koska ritareita on 24, on vähintään kahden ritarin oltava (jollakin) samalla etäisyydellä 
omasta paikastaan. Siis jos pöytää kierretään askelta, nämä vähintään kaksi ritaria saadaan omille paikoilleen.
24 ei ole tässä mikään taikaluku, sillä kyyhkyslakkaperiaate kyllä soveltuu muihinkin vastaavankaltaisiin tilanteisiin. 24 on vain valittu siksi, ettei kaikkien järjestysvaihtoehtojen läpikäynti yksi kerrallaan olisi ihan liian helppoa, mutta toisaalta ei liian vaikeaakaan.
Kysyin alkuperäisen jutun kommenttiosiossa, onnistuuko kierto enää välttämättä, jos yksi ritari olisikin istunut oikealle paikalle. Näkemykseni mukaan tässä tapauksessa ainakaan kyyhkyslakkaperiaatetta ei voida soveltaa, sillä väärille paikoille istuneet 23 ritaria ovat nyt 1–23 paikan päässä oikealta paikaltaan. Luultavasti on mahdollista konstruoida tilanne, jossa kiertämällä ei saada kuin yksi ritari kerrallaan paikalleen. En tosin ole nyt ihan varma. Todistakaapa tämä joko todeksi tai epätodeksi.
Muokattu 29.9.2015 – Neuvokas lukijamme Antti S. esittää alla mainion todistuksen sille, että homma onnistuu, vaikka yksi ritareista istuisikin aluksi epähuomiossa omalle paikalleen.
Todistusta ei heru, mutta kokeellista näyttöä sen verran, että kävin läpi 620 000 pöyditystä, joissa 24:stä ritarista yksi ritari on paikoillaan, enkä löytänyt yhtään sellaista, jossa ei kahta ritaria saisi paikoilleen.
Mielenkiintoista kyllä, parittomilla ritarimäärillä tällaisten pöyditysten löytäminen on helpompaa, ainakin nämä kaikki löytyivät nopeasti:
Seitsemän ritaria: 7 5 1 4 6 3 2
Yhdeksän ritaria: 4 1 7 2 6 8 3 5 9
Yksitoista ritaria: 9 3 10 4 7 11 5 1 8 2 6
Kolmetoista ritaria: 5 10 2 11 1 4 9 8 12 7 3 13 6
Viisitoista ritaria: 6 2 4 12 11 3 14 7 5 13 9 1 15 8 10
Seitsemäntoista ritaria: 15 13 6 9 5 4 16 10 2 1 12 8 17 3 14 11 7
Rohkenen näillä näytöillä väittää, että parillisilla määrillä pöyditys löytyy aina, parittomilla ei välttämättä. Kokeilin 19 ritaria, mutta siinä prosessilta loppui muisti ennenkuin ratkaisu löytyi, joten isommilla parittomilla seteillä ratkaisun löytäminen on ainakin vaikeampaa, seitsemällätoista se löytyi kokeilemalla alle 100 000 pöyditystä.
Kokeellisesta näytöstähän me matemaatikot emme perinteisesti ole olleet järin vakuuttuneita. 😉 Mutta mielenkiintoinen havainto. Yleistyisiköhän alla esiteltävällä todistuksella suuntaan tai toiseen. Seuraava ongelma on sitten miettiä, yleistyykö tulos, jos oikein istuneita ritareita on enemmän kuin kaksi.
Nykyään laskentatehon ollessa mitä on (ja yhä parantuessa) suhtautuminen koneellisiin todistuksiin saattaa olla vähitellen muuttumassa. Ilmeisesti ainakin joissakin tilanteissa tietokoneajo on jo ihan oikeasti hyväksytty todistukseksi. Muistelisin lukeneeni aiheesta jotain Matt Parkerin mainiosta Things To Make And Do In Fourth Dimension -kirjasta.
Eikös kaikilla parittomilla ritarimäärillä kelpaa seuraavanlainen järjestys: Oletetaan, että 1 istuu omalla paikallaan ja että pöytäkortit kiertävät vastapäivään numerojärjestyksessä. Tällöin kun laitetaan muut ritarit istumaan numerojärjestyksessä kiertäen myötäpäivään, saadaan järjestys, jossa jokaisella kierrolla on vain yksi ritari oikealla paikallaan.
Vaikuttaa pätevältä.
Kyselit todistusta tilanteelle, jossa yksi ritari istuu oikealla paikallaan…
Tällöinkin löytyy kierron määrä, jolla saadaan vähintään kaksi ritaria oikealle paikalleen. Todistetaan tämä epäsuorasti. Tehdään siis vastaoletus, että ei ole olemassa kiertoa (pöytää kierretään siis jotakin nollan ja 23 istumapaikan väliltä), jolla vähintään kaksi ritaria on oikeilla paikoillaan.
Millään kierron määrällä ei myöskään voi tulla vastaan tilanne, jossa kukaan ritari ei ole omalla paikallaan, sillä tällöin tilanne palautuisi alkuperäiseen kysymykseen. On siis oltava, että kullakin kierron määrällä täsmälleen yksi ritari on oikealla paikallaan.
Olkoon alkuperäisessä tilanteessa ritari 1 oikealla paikallaan. Kertokoon funktio d, kuinka monta istuinta pielessä kukin ritari istuu (laskenta vastapäivään). Siispä d(1)=0. Nyt ei ole olemassa kahta ritaria, joilla olisi sama d:n arvo, sillä tällöin olisi mahdollista kiertää pöytää niin, että vähintään kaksi olisi oikeilla paikoillaan. Siispä löytyy ritari, joka on yhden paikan päässä oikeasta paikasta, ritari, joka on kahden paikan päässä oikeasta paikasta jne. aina ritariin, joka on 23 paikan päässä oikeasta paikasta.
No sitten… ajatellaan ritaria 2, joka istuu väärällä paikalla. Liikutaan tältä paikalta myötäpäivään niin kauan, että löytyy ritari, jonka pitäisi istua paikalla, jolla kakkosritari istuu. Jatketaan taas tästä ritarista myötäpäivään niin kauan, että löytyy ritari, jonka pitäisi istua tämän ritarin paikalla ja niin edelleen. Huomataan, että jossakin vaiheessa päädytään takaisin ritariin kaksi (yhden tai useamman muun ritarin kautta). Se kuinka paljon on tullut liikuttua, voidaan nyt näppärästi laskea d:n arvojen avulla. Huomataan myös, että pöytä on tullut kierrettyä yhden tai useamman kerran, eli saatu summa on joku 24:n monikerta. Mikäli syntynyt ketju ei sisällä kaikkia 23:a väärillä paikoilla istuvaa ritaria, napataan joku ketjun ulkopuolelle jäänyt ritari ja muodostetaan uusi ketju ja jatketaan näin kunnes kaikki väärillä paikoilla istuvat ritarit kuuluvat johonkin ketjuun. Nyt kun lasketaan kaikkien ketjujen sisältämät d:n arvot yhteen, saadaan tulokseksi joku 24:n monikerta.
Vastaoletuksen vallitessa, kuten todettiin, d:n arvot ovat 0, 1, 2, … , 23. Näiden summa on 276, joka ei ole jaollinen 24:llä. Vastaoletus on siis hylättävä ja todettava, että on oltava vähintään kaksi ritaria, joilla on sama d:n arvo ja näin ollen pöytä voidaan kiertää asentoon, jossa vähintään kaksi ritaria istuu oikeilla paikoillaan.
Mahtavaa! Kiitos!
No niin, tällä tulee siis todistetuksi se, mihin kokeelliset tulokseni jo viittasivatkin: ratkaisun löytyminen riippuu pariteetista, koska d(n) / n kasvaa aina puolikkaalla, kun n kasvaa yhdellä.
Parillisilla ritarien määrillä pöydässä on aina kaksi ritaria, jotka osuvat paikoilleen, parittomilla taas on mahdollista laatia pöyditys, jossa yhtä useampaa ritaria ei osu oikealle paikalle, vaikka kuinka pyörittäisi.