Pulmatehtävä Die Hard 3 -elokuvasta

Die Hard 3 -leffassa John McClane (Bruce Willis) ja Zeus (Samuel L. Jackson) joutuvat ratkaisemaan seuraavan pulmatehtävän saadakseen pommin deaktivoitua:

Käytössä on 3L ja 5L vesiastiat sekä suihkulähde, josta saa vettä (rajattomasti). Astian saa täyttää täyteen tai kaataa tyhjäksi ja astiasta saa kaataa vettä toiseen astiaan; astioissa ei kuitenkaan ole mitään mitta-asteikkoja. Tehtävänä on mitata tasan 4L suuruinen vesimäärä 5L astiaan. (Toiseen astiaan tällöin jäävä vesimäärä on epäoleellinen.) Kuinka tulee toimia?

Katso elokuvan pulmatehtäväpätkä

"...Hey!...You wanna focus on the problem at hand?"

Lisätehtäviä

• Mikäli vesiastioiden tilavuudet olisivat 3L ja 6L ja tehtävänanto muuten sama, olisiko tehtävä mahdollinen? Miksi? Entä jos tilavuudet olisivat 7L ja 10L?
• Miksi alkuperäinen tehtävä ylipäätään on mahdollinen? Mikä ehto vesiastioiden tilavuuksien on siis täytettävä, jotta tehtävä onnistuu (jos oletetaan, että tilavuudet ovat positiivisia kokonaislukuja)? (vinkki: liittyy lukuteoriaan ja nk. Diofantoksen yhtälöön)
• Kuinka tehtävän voi ratkaista verkkoteorian avulla?

Ratkaisu

Piirretään seuraavanlainen tehtävänannon ehtojen mukainen suunnattu verkko:

Verkon kärkinä (solmuina) ovat astioissa olevat vesilitramäärät siten, että selvästikin merkinnässä (x,y) muuttuja x tarkoittaa veden määrää 3L astiassa ja vastaavasti y veden määrää 5L astiassa. (Miksi väliin "jäävät kärjet" eivät kuulu verkkoon?)

Nyt halutaan siis oleellisesti löytää reitti suunnatulla verkolla kärjestä (0,0) kärkeen (0,4) tai (3,4). Itse asiassa, jos toinen edellä mainituista löydetään, saadaan toinen helposti jatkamalla yhden pykälän eteenpäin (joko täyttämällä tai tyhjentämällä kolmen litran astia tilanteen mukaan).

Huomaa, että halutaan päästä joko solmuun (kärkeen) (0,4) tai (3,4), sillä vain näissä viiden litran astiassa on vaadittu 4L vesimäärä. Tutkimalla havaitaan, että tehtävänannon ehdot toteuttava reitti on:

(0,0), (0,5), (3,2), (0,2), (2,0), (2,5), (3,4)

ja mikäli halutaan niin lopuksi vielä (0,4). Muitakin ratkaisuja saattaa olla, en ole etsinyt. Tarkennus 25.9.2007: Ratkaisuja on ääretön määrä (kuvassa voidaan halutessa "kiertää" pidempäänkin ennen kärkeen (0,4) tai (3,4) menemistä), mutta "mahdollisimman lyhyitä reittejä" on kuitenkin vain kaksi.

Kiitos tehtävästä mainitsemisesta ja yllä esitetystä ratkaisusta kuuluu kesäkuussa suorittamani Johdatus diskreettiin matematiikkaan -kurssin opettajalle, Markku Vilppolaiselle.

LISÄYS 7.9.2007

Annoin Klassikan MAA1-ryhmälleni eilen torstaina tämän tehtävän oppitunnin alussa mietittäväksi. Löppösen Anni ja Pesosen Johanna ratkaisivat tehtävän ja kävivät myös ansiokkaasti taululla selittämässä ratkaisunsa luokalle. Annin ratkaisu oli edellä esittämätön, mutta kaaviokuvasta luettavissa oleva

(0,0), (3,0), (0,3), (3,3), (1,5), (1,0), (0,1), (3,1), (0,4).

Johanna esitti saman ratkaisun kuin minä alunperin. Molemmat keksivät ratkaisun kirjaimellisesti muutaman minuutin miettimisellä ilman kynää ja paperia, itseltäni kesti pidempään :)

LISÄYS 25.9.2007

Huomaa, että nk. Diofantoksen yhtälö, eli yksi yhtälö, jossa on kaksi tuntematonta, liittyy juuri samaiseen asiaan ja Diofantoksen yhtälön avulla voi ratkaista tämän tehtävän analyyttisesti (laskennallisesti). Diofantoksen yhtälöä käsitellään lukion pitkän matematiikan kurssilla 11, Logiikka ja lukuteoria. Katso myös uskoakseni samaiseen kreikkalaiseen matemaatikko Diofantokseen liittyvä pulmatehtävä.