חידות לוגיות

V jednom městě tvoří síť ulic pravidelnou čtvercovou mřížku N×N. Z jihozápadního rohu (označme bod A) si vyšel na procházku strýček Pepin a směřuje k severovýchodnímu rohu (označme bod B). Vždy volí ulici na sever nebo na východ. Ve stejnou chvíli z bodu B vychází na procházku tetička Žofinka a jejím cílem je bod A. Vždy volí ulici na jih nebo na západ.
Jaká je pravděpodobnost, že se na některém z rohů potkají?
Když půjde Pepin třikrát rychleji jak Žofinka, jaká je pak pravděpodobnost, že se na některém z rohů potkají?

Show/hide solution:

Nejprve je nutné si uvědomit, že se mají šanci setkat pouze právě po N krocích (jindy už ne). Záleží také velmi na tom, jakou cestu Pepin zvolí. Když například půjde stále na východ, tak je menší pravděpodobnost, že se potkají než když se vydá do středu města. Proto musíme brát v úvahu i pravděpodobnost, s jakou Pepin danou cestu zvolí. Různé cesty, které končí po N krocích ve stejném bodě jsou ekvivaletní a je jedno, kterou z nich vybere. Protože vždy volí mezi dvěma cestami, jde jeho volba napsat jako sekvence 0 a 1 délky N. Ekvivalentní jsou tedy řetězce se stejným počtem 0 a 1.
Aby se s ním Žofinka potkala tak musí mít ve svých rozhodnutích také stejný počet jedniček (1 pro východ a jih, 0 pro sever a západ).
Různých cest délky N je celkem 2^N. Z toho cest, které obsahují K jedniček, je N nad K (vychází z Pascalova trojúhelníka) tedy N!/(K!(N-K)!). Tedy pravděpodobnost, že Pepin zvolí cestu s K jedničkami je (N!/(K!(N-K)!)/(2^N) a pravděpodobnost, že zároveň Žofinka zvolí cestu se stejným počtem jedniček je (N!/(K!(N-K)!)/(2^N) * (N!/(K!(N-K)!)/(2^N) = ((N!/(K!(N-K)!)/(2^N))^2.
Celková pravděpodobnost setkání je tedy suma daného výrazu přes všechny K od 0 do N: tedy suma(K=0..N)(((N!/(K!(N-K)!)/(2^N))^2).

» גלריה » חידות לוגיות 111000100001110110