задачка

[avva]

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

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



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

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

Comments

[ded-maxim.livejournal.com]

Вообще-то, эту задачу можно решить и без теории просачивания. Элементарная комбинаторика. Теория просачивания нетривиальна только тогда, когда в решётке бесконечное число узлов.

[myxomop.livejournal.com]

Ну, не совсем элементарная. 2¹³ вариантов.

А в институте это решалось декомпозицией по Шеннону.

[ded-maxim.livejournal.com]

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

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

[hotgiraffe.livejournal.com]

понятно, что для конечных сеток (тем более небольших) пишется нудная, но несложная по сути формула

например, счесть систему мостов электрической цепью, написать общее сопротивление системы по правилу Кирхгофа, а потом сосчитать количество ноликов в таблице общих сопротивлений, когда каждое из составляющих - 0 или не-0 )))