Gnedenkon probleema

Seuraava kombinatorinen tehtäväkokonaisuus on improvisoiden käännetty B.W.Gnedenkon teoksesta

Lehrbuch der Wahrsceinlichkeitsrechnung, Berlin 1962.

Ensimmäinen kysymys on lukiolaisen kannalta perustehtävä mutta muut ehkä vaativat pohtimista. Ongelman ratkaisu on tavallaan piilotettu tälle sivulle!

Kuvassa on koordinaatistoon piirretty hila. Vaaka-akselin pisteet ovat (0,0), (2,0), (4,0), ... ,(2n,0). Hilassa on (n+1)*(n+1) pistettä.

1. Kuinka monella tavalla voidaan edetä pisteestä (0,0) pisteeseen (2n,0), kun edetään pollukoita pitkin vasemmalta oikealle valitsemalla aina jompikumpi lähinnä etuviistossa oleva pollukka?

2. Kuinka monella tavalla eteneminen voidaan suorittaa vaaka-akselin alapuolella ylittämättä vaaka-akselia kertaakaan? (Akselilla saa käydä mutta sitä ei saa ylittää.)

3. Teatteriin on tulossa 2n henkilöä, joista n:llä on mukanaan viisikymppinen ja lopuilla satasen seteli. Teatterilippu maksaa viisikymmentä markkaa. Teatterin lipunmyyjällä ei ole vaihtokassaa. Millä todennäköisyydellä lipunmyyjän ei tarvitse lähteä vaihtamaan rahaa kesken lipunmyynnin?

010196 M.H.