[Tikimybių teorija, kombinatorika] Atsitiktinės gatvės

Vienas miestas yra labai taisyklingos formos: jis yra n x (n - 1) stačiakampis, sudarytas iš 1 x 1 kvadratinių kvartalų. Bet kurį kvartalą riboja keturios gatvės (kiekviena gatvė yra tarp dviejų kvartalų arba tarp kvartalo ir užmiesčio). Pavyzdžiui, jei n = 5, tai miestas atrodo taip (aukštis - 4, plotis - 5):
_ _ _ _ _
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|_|_|


Kažkodėl miestas buvo apleistas ir dabar kai kurios gatvės yra užgriuvusios ir nepraeinamos. Laikykime, kad kiekvienos gatvės būklė yra atsitiktinė: tikimybė 1/2, kad gatvė praeinama, ir tikimybė 1/2, kad gatvė nepraeinama. Gatvės būklė nepriklauso nuo kitų gatvių būklės.

Raskite tikimybę, kad miestą galima praeiti iš kairės į dešinę: galima pradėti bet kurioje kairiausioje sankryžoje, eiti tik neužgriuvusiomis gatvėmis ir baigti bet kurioje dešiniausioje sankryžoje.

AncientMarinerVienas miestas yra labai taisyklingos formos: jis yra n x (n - 1) stačiakampis, sudarytas iš 1 x 1 kvadratinių kvartalų. Bet kurį kvartalą riboja keturios gatvės (kiekviena gatvė yra tarp dviejų kvartalų arba tarp kvartalo ir užmiesčio). Pavyzdžiui, jei n = 5, tai miestas atrodo taip (aukštis - 4, plotis - 5):
_ _ _ _ _
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|_|_|


Kažkodėl miestas buvo apleistas ir dabar kai kurios gatvės yra užgriuvusios ir nepraeinamos. Laikykime, kad kiekvienos gatvės būklė yra atsitiktinė: tikimybė 1/2, kad gatvė praeinama, ir tikimybė 1/2, kad gatvė nepraeinama. Gatvės būklė nepriklauso nuo kitų gatvių būklės.

Raskite tikimybę, kad miestą galima praeiti iš kairės į dešinę: galima pradėti bet kurioje kairiausioje sankryžoje, eiti tik neužgriuvusiomis gatvėmis ir baigti bet kurioje dešiniausioje sankryžoje.

O man įdomu buvo ar galima eiti tik iš kairės į dešinę, ar galima paeiti ir atgal (į kairę), tam kad į teisingą kelią išeit?

Pirmame paveikslėlyje (iš kairės) pavaizduotas miestas pradinėje būsenoje, jei n = 4.

Kai kurias gatves (briaunas) ištriname. Kiekvienai briaunai atskirai metame monetą ir briauną ištriname, jei iškrenta herbas (taigi tikimybė, kad konkreti briauna ištrinta, yra 1/2, o skirtingų briaunų būsenos nepriklauso viena nuo kitos).

Antrame paveikslėlyje pavaizduota galima situacija, kai briaunos baigtos trinti. Trečiame paveikslėlyje raudonai paryškintas kelias, kuriuo galima pereiti iš kairio miesto pakraščio į dešinį (galima eiti ir į kairę).
Taigi antrame paveikslėlyje pavaizduotą miestą galima "pereiti iš kairės į dešinę".

Ketvirtame paveikslėlyje pavaizduota kita galima situacija, kai briaunos baigtos trinti. Tokiu atveju kelio iš kairio pakraščio į dešinį nėra - miesto negalima "pereiti iš kairės į dešinę".


Kitaip sakant, iš pradžių atsitiktinai triname briaunas, o po to žiūrime ar liko bent vienas kelias iš kairio krašto į dešinį. Kelias yra bet kokia seka neištrintų briaunų, kurioje paeiliui esančios briaunos yra gretimos mieste (taigi galima eiti iš kairės į dešinę, iš dešinės į kairę, iš viršaus į apačią ir iš apačios į viršų - bet kaip. Svarbu neiti ištrintomis briaunomis).

Jei gali kokią savaitę nerašyk atsakymo. Nerandu laiko prisėsti ramiai pagalvoti. Atrodo įdomus uždavinys. Panašų (bet labiau komplikuotą) dabar kaip tik darau atsitiktinių matricų spektro tematikoje.

AncientMariner

Pirmame paveikslėlyje (iš kairės) pavaizduotas miestas pradinėje būsenoje, jei n = 4.

Kai kurias gatves (briaunas) ištriname. Kiekvienai briaunai atskirai metame monetą ir briauną ištriname, jei iškrenta herbas (taigi tikimybė, kad konkreti briauna ištrinta, yra 1/2, o skirtingų briaunų būsenos nepriklauso viena nuo kitos).

Antrame paveikslėlyje pavaizduota galima situacija, kai briaunos baigtos trinti. Trečiame paveikslėlyje raudonai paryškintas kelias, kuriuo galima pereiti iš kairio miesto pakraščio į dešinį (galima eiti ir į kairę).
Taigi antrame paveikslėlyje pavaizduotą miestą galima "pereiti iš kairės į dešinę".

Ketvirtame paveikslėlyje pavaizduota kita galima situacija, kai briaunos baigtos trinti. Tokiu atveju kelio iš kairio pakraščio į dešinį nėra - miesto negalima "pereiti iš kairės į dešinę".


Kitaip sakant, iš pradžių atsitiktinai triname briaunas, o po to žiūrime ar liko bent vienas kelias iš kairio krašto į dešinį. Kelias yra bet kokia seka neištrintų briaunų, kurioje paeiliui esančios briaunos yra gretimos mieste (taigi galima eiti iš kairės į dešinę, iš dešinės į kairę, iš viršaus į apačią ir iš apačios į viršų - bet kaip. Svarbu neiti ištrintomis briaunomis).

verbunaiJei gali kokią savaitę nerašyk atsakymo.