задачка

[avva]

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

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



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

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

Comments

[ded-maxim.livejournal.com]

Я же сказал "элементарная", а не "прямолинейная". Комбинаторное решение только тогда интересно, когда оно проводится изящно, а не перебором. Нужно максимально эксплуатировать любую симметрию в условии задачи, например.

Что касается разложения по Шеннону, таки да, у него была пара статей на предмет надёжности релейных схем. А эту задачу можно также сформулировать в таком ключе. Потом те же самые формулы были получены в теории просачивания, но другими методами.