Putkaposti: Hyppykeppi

Tohtori Sykerön hyppykeppi on epäkunnossa: se vie Sykeröä satunnaisesti joko askeleen eteenpäin tai askeleen taaksepäin. Sykerö lähtee liikkeelle vesilammikon luota ja yrittää päästä aikakoneeseen, joka on tietyn askelmäärän päässä. Kuinka todennäköisesti Sykerö pääsee lopulta aikakoneeseen eikä molskahda lammikkoon?

Tehtävä

Hyppykeppi vie Sykeröä askeleen eteenpäin todennäköisyydellä p ja askeleen taaksepäin todennäköisyydellä 1 - p. Aikakoneeseen on matkaa n askelta. Heti askel Sykerön aloituskohdasta taaksepäin on vesilammikko, johon hyppääminen keskeyttää Sykerön matkanteon.

Tarkastellaan tilannetta, jossa Sykerö hyppää eteenpäin todennäköisyydellä 4/5 ja aikakoneeseen on matkaa 3 askelta (eli p on 4/5 ja n on 3). Nyt mahdollisia hyppysarjoja ovat esimerkiksi seuraavat:

1. eteen, eteen, taakse, eteen, eteen
2. eteen, taakse, taakse
3. eteen, eteen, taakse, taakse, eteen, taakse, eteen, eteen, eteen
4. eteen, eteen, taakse, eteen, taakse, taakse, taakse

Hyppysarjat 1 ja 3 johtavat aikakoneeseen, kun taas hyppysarjat 2 ja 4 johtavat vesilammikkoon. Erilaisia hyppysarjoja on ääretön määrä, koska Sykerö voi pomppia edestakaisin samoissa kohdissa. Tässä tapauksessa todennäköisyys, että Sykerö pääsee aikakoneeseen, on 64/85 ≈ 0,75294.

Tiedostossa hkeppi.txt on joka rivillä yksi p:n ja n:n arvo. Tehtävänä on laskea kussakin tapauksessa todennäköisyys, että Sykerö pääsee aikakoneeseen.

Vastausohje

Vastauksen jokaiselle riville tulee yksi todennäköisyys loppuun asti sievennetyssä murtolukumuodossa. Todennäköisyydet voi ilmoittaa missä tahansa järjestyksessä, ja jokainen todennäköisyys on yli 0 ja alle 1.

Vastaus voisi näyttää seuraavalta:

64/85

Tämä on esimerkin oikea vastaus, mutta tätä tapausta ei ole tiedostossa hkeppi.txt.