Sunnuntaipähkinä 15: Lewis Carrollin apinaongelma

Apina roikkuu kuvan tapaan väkipyörän yli vedetyssä köydessä punnuksen kanssa tasapainossa. Oletetaan väkipyörä kitkattomaksi. Mitä tapahtuu punnukselle, jos apina alkaa kiivetä köyttä pitkin?
Lewis Carroll kuvasi ongelman päiväkirjassaan vuonna 1893 ja kummasteli, kuinka hyvät matemaatikot voivat päätyä niin erilaisiin vastauksiin. Mille kannalle sinä päädyt? Ratkaisu kerrotaan ensi sunnuntainpähkinän yhteydessä.
Viime sunnuntaipähkinän ratkaisu: Ongelman ratkaisi vuonna 1736 maineikas matemaatikko Leonhard Euler. Samalla hän tuli antaneeksi alkusysäyksen verkkoteoriaksi nykyään kutsutulle tieteenalalle. Siihen pohjautuu viime aikoina verkostojen teoria, joka tutkii todellisen maailman verkostojen ominaisuuksia.
Nykyään verkostojen teorian avulla selitetään useita asioita ihmisten muodostamien verkotostojen toiminnasta tietojenkäsittelytieteeseen ja biologiaan. Se on aiheuttanut suoranaisen paradigman muutoksen monilla tieteen- ja muun inhimillisen toiminnan aloilla.
Verkkoteoria oli kuitenkin pitkään matemaattista perustutkimusta ilman kummempia sovelluksia — kaiken maailman dosenttien näpertelyä. Olkoon tämäkin muistutuksena, että etukäteen on hankala tietää, millä ajatuksilla tai minkälaisella tutkimuksella on tulevaisuudessa ratkaiseva rooli.
Asiaan. Pähkinän vastaus on, että tällaista reittiä ei ole.
Euler ratkaisi ongelman määrittelemällä ensin eräitä verkostojen käsitteitä. Verkosto koostuu solmuista ja kaarista eli linkeistä. Kuvataan maa-alueet solmuina ja niitä yhdistävät sillat kaarina kuvan tapaan.

Köningsbergin sillat esitettynä verkostona. Kuva pohjautuu Wikimedia Commons -kuviin. CC-BY-2.0, Terra Cognita.

Maa-alueet ja niitä vastaavat solmut on kuvattu kirjaimilla A, B, C ja D. Kun lasketaan kuhunkin solmuun tulevat kaaret, nähdään että A:lla niitä on 3, B:llä on 5, C:llä on 3 ja D:llä on 3. Koska kaikkiin saapuu pariton määrä kaaria, kutsutaan solmuja paritomiksi solmuiksi. Parillinen solmu on sellainen, johon kiinnittyy parillinen määrä kaaria.
Euler tutki verkostojen ominaisuuksia ja havaitsi, että parittoman solmun on oltava joko polun alku- tai päätepiste. Koska kaikkien solmujen läpi kukevassa reitissä on yksi alku ja loppupiste, siinä ei voi olla enempää kuin kaksi paritonta solmua. Toisin sanoen jos verkostossa on enemmän kuin kaksi paritonta solmua, sen läpi ei voi kulkea siten että kulkisi kunkin kaaren kautta tasan kerran.
Koska Köningsbergin siltaongelmassa parittomia napoja on kahden sijasta neljä, kysyttyä reittiä ei ole.
(Lisäys 28.2.2016 klo 18:01) No niin. Hopussa kirjoitin ratkaisun ja jälki oli tietysti sen mukaista. Kiitos Matti K. Sinisalolle tarkkaavaisuudesta ja korjauksesta. Lisäksi pahoitteluni virheestä. Seuraavassa esitetään korjattu ratkaisu.
Itse ongelma voidaan siis ratkaista seuraavalla yksinkertaisella päättelyllä: Jotta olisi mahdollista kulkea jokaisen sillan yli tasan kerran, jokaisesta ma-alueesta pitäisi välttämättä lähteä yhtä monta siltaa kuin siihen tulee. Siltoja täytyy siis olla jokaista maa-aluetta kohti parillinen määrä. Koska jokaisesta maapalasta lähtee pariton määrä siltoja, tehtävä ei ole mahdollinen.
Ja mitä Euleriin ja verkkoteoriaan tulee, Euler todisti, että verkkoon on mahdollista piirtää sellainen polku, joka kulkee jokaisen kaaren kautta tarkalleen kerran ja palaa lähtöpisteeseensä jos ja vain jos verkossa ei ole yhtään paritonta solmua. Tällaista polkua kutsutaan Eulerin kehäksi.
Koska Köningsbergin siltaongelmassa parittomia solmuja on peräti neljä, tehtävä ei ole mahdollinen.