Ménage à quatre

Hyvin tunnetussa (ja varsin helpossa) matemaattisessa ongelmassa pitää kuljettaa susi, lammas ja kaali veneellä joen yli, johon soutajan lisäksi mahtuu vain yksi muu matkustaja. Jutun juju on tietenkin se, että ellei soutaja ole paikalla vahtimassa, syö susi lampaan ja lammas kaalin. Kysymys kuuluu, kuinka nämä saadaan yhtenä kappaleena joen yli. Ratkaisepa tämä ensin, ellet ole jo ratkaissut!

Ian Stewart pistää kirjassaan Another Fine Math You’ve Got Me Into… vielä paremmaksi. Nyt kuljetettavana on mörkö, susi, lammas ja kaali, eikä veneeseen edelleenkään mahdu soutajan lisäksi kuin yksi muu matkalainen. Susi syö yhä lampaan ja lammas kaalin, ellei niitä valvota. Mörkö puolestaan iskee valvomattomana välittömästi hampaansa suteen, mikäli paikalla ei ole kaalia (jota se ei syö). Saadaanko retkue toisiaan popsimatta joen toiselle penkalle?

Kuva: Hasibul Haque Sakib/Flickr (CC BY-NC 2.0)

Ratkaisu: Kuljetus onnistuu, vaikka mörkö onkin häiritsemässä. Ongelman voi ratkaista ihan päättelemälläkin, mutta mielestäni yksi kiehtova ratkaisutapa on tehdä geometrinen visualisointi tilanteesta. Näin tulkittuna ongelma on sukua taannoiselle muurahaisen vaikealle juoksulle.

Ratkaisuun tarvitaan tesseraktia eli neliulotteista hyperkuutiota, joka on muuten ihan samanlainen kuin tavallinen kolmiulotteinen kuutio, mutta sen jokaisessa kärjessä kohtaa neljä särmää kolmen sijasta.

Kuva: Sonja Šumonja/Geogebratube (CC BY-SA); muokkaus Hannu Sinisalo

Tavoitteena on päästä (kaali, lammas, susi, mörkö)-koordinaatiston pisteestä $(0, 0, 0, 0)$ pisteeseen $(1, 1, 1, 1)$ , jossa jokainen koordinaatin vaihto vaihtaa yhden siirreltävän luontokappaleen paikkaa joen yhdeltä puolelta toiselle. Jokaisen koordinaatin vaihto vastaa tesseraktin yhden särmän kulkemista. Jokaisessa tesseraktin kärjessä osa särmistä poissuljetaan mahdottomina ja lopuista valitaan reitti, jolla jatketaan eteenpäin.

Ensimmäinen siirrettävä on oltava lammas. Siis ensimmäinen piste, johon origosta päädytään on pakko olla $(0,1,0,0)$ . Tämän jälkeen viedään mörkö, eli siirrymme pisteeseen $(0,1,0,1)$ . Sitten viedään kaali siirtymällä pisteeseen $(1,1,0,1)$ ja tuodaan lammas takaisin siirrolla $(1,0,0,1)$ . Sitten viedään susi $(1,0,1,1)$ , ja lopulta viimeiseksi viedään lammas uudestaan $(1,1,1,1)$ .