задачка

[avva]

Хорошую задачку подсмотрел у cousin_it (там ещё есть несколько геометрических, если кому интересно).

Река, острова на ней и система мостов между островами выглядят так:



В результате наводнения каждый мост смывает независимо от других с вероятностью 1/2. Какова вероятность того, что через реку можно будет перебраться?

Наверняка хорошо известная, но мне раньше не попадалась. Получил удовольствие от процесса решения.

Comments

[(Anonymous)]

Забавно, стал рассказывать жене, и понял, что надо куда аккуратнее-подробнее, а именно: каждой связной реализации на нашем куске соответствует сломанная на дуальном, и значит, такая же сломанная на нашем. То бишь, каждой связной реализации есть парная сломанная. А вероятность каждой реализации -- одна и та же, половина в степени кол-во ребер. И вот только теперь -- следовательно, мера связных реализаций равна мере сломанных, значит -- половина.