tuloperiaate

Kuutio Muurahainen lähtee liikkeelle kuution kärjestä $A$ ja etenee kuution särmiä pitkin. Kun muurahainen tulee johonkin kärkeen, se valitsee sattumanvaraisesti seuraavan särmän, jota pitkin se lähtee kulkemaan (se voi siis myös palata takaisin kohti kärkeä, josta se juuri lähti). Millä todennäköisyydellä muurahainen päätyy kärkeen $B$ kuljettuaan täsmälleen seitsemän särmää?

(HUOM! Muurahaisen ei tarvitse olla seitsemännen särmän jälkeen ensimmäistä kertaa kärjessä $B$ .)

Tämä ongelma on huomattavasti haastavampi kuin Muurahaisen helppo juoksu, joten suosittelen tutustumaan tähän vasta helpolla juoksulla lämmiteltyäsi.

Ratkaisu: Harva ongelma (edes tässä blogissa) on saanut minut innostumaan yhtä paljoa kuin tämä. Syy siihen on seuraavassa kerrassaan hurmaavassa tavassa ratkaista pulma.

Koska kaikki kulkureitit ovat yhtä todennäköisiä, päästään ongelman ratkaisussa soveltamaan klassista todennäköisyyttä. Kun liikutaan seitsemän särmää, ja jokaisessa kärjessä on kolme vaihtoehtoa seuraavaksi suunnaksi, on erilaisia kulkureittejä tuloperiaatteen nojalla $3^7=2187$ kappaletta. Selvitetään seuraavaksi, kuinka moni näistä reiteistä on suotuisia tapauksia muurahaisellemme.

Olkoon piste $A=(0,0,0)$ ja piste $B=(1,1,1)$ . Jokaisen särmän liikkuminen muuttaa täsmälleen yhtä pisteen kolmesta koordinaatista, nollasta ykköseksi tai ykkösestä nollaksi. Tavoitteemme olisi siis se, että kaikkia koordinaatteja olisi seitsemän särmän jälkeen muutettu pariton määrä kertoja. Tämä voidaan tehdä kahdella ja vain kahdella erilaisella tavalla:

Yhtä koordinaattia muutetaan viidesti ja kahta muuta kerran.
Kahta koordinaattia muutetaan kolmesti ja yhtä kerran.

Lasketaan sitten, montako erilaista reittiä tapauksiin 1 ja 2 sisältyy. Viidesti muutettava koordinaatti voidaan valita kolmella tavalla. Edelleen kombinatoriikkaa soveltaen viisi vaihtoa seitsemästä voidaan valita $\binom{7}{5}=\frac{7!}{5!2!}=21$ tavalla. Jäljelle jäävien koordinaattien vaihdoista ensimmäinen voidaan valita kahdesta jäljellä olevasta vaihtopaikasta, jolloin viimeiselle koordinaatin vaihdolle jää vain yksi paikka. Näin ollen tapaukselle 1 suotuisia reittejä on

$3\cdot\binom{7}{5}\cdot 2\cdot 1=126.$

Vastaavaa päättelyä noudattaen tapaukseen 2 sisältyy $3\cdot\binom{7}{3}\cdot \binom{4}{3}\cdot 1=420$ mahdollista reittiä. Koska tapaukset 1 ja 2 ovat erilliset, eli niihin ei sisälly samoja reittejä, on reittien kokonaismäärä $126+420=546$ Näin ollen todennäköisyys sille, että seitsemännen särmän jälkeen ollaan kärjessä $B$ on klassisen todennäköisyyden mukaan

$\frac{546}{2187}=\frac{182}{729}=0,2496\ldots\approx 0,25.$

Tästäkin ongelmasta iso kiitos Thomas Poveylle, jonka pulmakirjaa Professor Povey’s Perplexing Problems olen nyt pari viikkoa iltaisin jatkuvasti selaillut. Kirjassa on kymmeniä tiukkoja matematiikan ja fysiikan tehtäviä, jotka on suunnattu korkeakouluopintojen kynnyksellä oleville ongelmanratkaisusta innostuneille opiskelijoille. Tai sitten heidän opettajilleen. Erittäin suositeltava opus.

PS. Eräs opiskelijani heitti suunnilleen välittömästi ongelman kuultuaan arvauksen, että vastaus ei varmaankaan ole $\frac{1}{4}$ , mutta että se on sinnepäin. Aivan oikein. Parittomalla siirtomäärällä kuutiossa on vain neljä kärkeä, joissa muurahainen voi olla. Mitä suuremmaksi siirtojen määrä kasvaa – kunhan niitä on vain pariton määrä – sitä lähempänä todennäköisyys päätyä kärkeen $B$ on arvoa $\frac{1}{4}$ .

Ratkaisu: Jokaisessa kärjessä muurahaisella on kolme vaihtoehtoa seuraavalle suunnalle, joten erilaisia kolmen särmän reittejä on tuloperiaatteen mukaan $3\cdot 3\cdot 3=27$ .

Mietitään sitten, kuinka moni reiteistä vie kolmea särmää pitkin kärkeen $B$ . Kärki $A$ on ainoa kärki, josta etäisyys kärkeen $B$ on $3$ särmää. Kustakin kärjestä, johon kärjestä $A$ pääsee, etäisyys on $2$ särmää. On samantekevää, mikä suunta valitaan ensin – sopivia vaihtoehtoja on siis $3$ . Toisessa kärjessä on aivan sama, minne muurahainen jatkaa matkaansa, kunhan se ei palaa takaisin. Vaihtoehtoja on siis $2$ . Kolmannesta kärjestä on yksi reitti kärkeen $B$ . Näin ollen suotuisia reittejä on $3\cdot 2\cdot 1=6$ .