Hieman olen miettinyt, kuinka paljon vielä kehtaan tänne Alex Bellosin loistavaa The Guardianin pulmapalstaa suomentaa, mutta menköön nyt vielä ainakin tämän kerran. Voi kai tätä jonkinlaisena toimituksellisena työnä sentään pitää. Tämänkertainen pulma on mukaelma muutaman vuoden takaa The New York Timesissa julkaistusta ”prinsessapulmasta”. Ja tässä se tulee.

Käytävällä on ovia rivissä, ja yhden oven takaa löytyy kissa. Kissa! Sinun tehtäväsi on löytää kyseinen luomakunnan kruunu. Mutta säännöt ovat vaativat: saat arvata vain kerran, jonka jälkeen kissa siirtyy (näennäisen!) sattumanvaraisesti yhden oven joko oikealle tai vasemmalle.

Viikon helppo pulma on löytää kissa korkeintaan neljännellä arvauksella, kun ovia on rivissä neljä.

Viikon vaikea pulma on selvästi haastavampi: mikä on pienin määrä arvauksia, joilla löydät kissan varmasti, kun kissa piileskelee seitsemän oven takana?

Selvennyksiksi vielä todettakoon, että kissa siirtyy jokaisen arvauksen jälkeen, ja että ovet ovat tosiaankin rivissä, eli vasemmanpuolimmainen ja oikeanpuolimmainen ovi ovat käytävän reunoilla, eikä niistä ole yhteyttä toisiinsa ”nurkan ympäri”.

Kuva: Abby Rosenberg / Flickr (CC BY-NC 2.0)

Ratkaisu: Tämä pulma on erinomainen esimerkki eräästä matemaattisesta ongelmanratkaisumenetelmästä, jossa monimutkaista pulmaa lähestytään ennen yksinkertaisemman erikoistapauksen kautta ja sitten pyritään löytämään menetelmä, joka sopii myös monimutkaisemmille tapauksille. Ajatellaanpa vaikka tätä pulmaa yksinkertaisimmillaan. Jos ovia olisikin vain yksi, olisi kissa varmasti sen takana. Jos taas ovia olisi kaksi, niin ellei kissa heti olisi arvatun oven takana, siirtyisi se sinne seuraavaksi kerraksi. Oikeastaan kolmen oven versio on ensimmäinen mielekäs vaihe, jossa yksi pulman lopulliselle ratkaisemiselle keskeinen idea tulee ensimmäistä kertaa esiin: jos kissa ei ole keskioven takana, on sen oltava reunassa, josta se siirtyy keskioven taakse seuraavalle kierrokselle. Kissa ei siis voi olla kahta kertaa peräkkäin reunaoven takana.

Tehdään nyt ratkaisuista kaaviokuvat. Merkitään avattua ovea A:lla ja mahdollista kissan paikkaa K:lla. Esittelen tässä nyt pisimmät tiet – kissahan voisi hyvällä onnella tulla vastaan jo aiemminkin. Mutta seuraavat reitit johtavat varmasti ratkaisuun. Neljän oven ratkaisualgoritmi on seuraava:

Pienellä pohdinnalla ratkaisumalli alkaa hahmottua. Muutamia huomioita voi tehdä nopeasti. Ei kannata aloittaa reunalta, se ei johda mihinkään. Jos kissa on reunalla, ei se voi seuraavalla kerralla siellä olla. Jos tästä laajennetaan viiden oven tapaukseen, huomataan myös se, että keskimmäisestä ovesta aloittaminen ei myöskään toimi. Miten voidaan alkaa rajoittaa kissan paikkoja? Voidaanko osa ovista rajata pysyvästi kissavapaaksi alueeksi?

Itse painin aika tovin viiden oven ongelman kanssa, mutta sitten juttu alkoi aueta. Sen innoittamana kuuden oven versio ratkesi nopeasti, eikä seitsemän ovea ollut sitten enää sen kummempi haaste. Alex Bellosin linkkaaman alkuperäisen pulman ovien lukumäärä oli 17, mutta sama ratkaisualgoritmi toimii siihenkin. Jos ovia on kappaletta, arvauksia tarvitaan aina korkeintaan . Tässä ratkaisu seitsemälle ovelle. Arvauksia tarvitaan korkeintaan kymmenen. En selitä enempää. Tutki itse (ja tule vasta sitten tarkistamaan ratkaisu)!