Задача про мост

[Render]

Есть мост через реку. Он сложен из одинаковых перекладин в виде сетки m*n. То есть на каждом берегу лежит по m+1 концов.
После штурма каждая перекладина уцелела с вероятностью 0.5. Найти вероятность, что остался путь через реку по мосту.
Хотелось бы придумать что-то лучше простого перебора.

[Профессор Снэйп]

Если я правильно понял, на математическом языке задача формулируется следующим образом.

Есть неориентированный граф, множеством вершин которого является множество

$$ V = \{ v_{i,j} : 0 \leqslant i \leqslant n,\, 0 \leqslant j \leqslant m \} $$

Для каждых $i,k \leqslant n$ и $j,l \leqslant m$ если $|i-k|+|j-l|=1$, то вершины $v_{i,j}$ и $v_{k,l}$ соединены ребром с вероятностью $1/2$. Если же $|i-k|+|j-l| > 1$, то вершины $v_{i,j}$ и $v_{k,l}$ не соединены ребром.

Требуется найти вероятность того, что в графе существует путь, начинающийся в вершине $v_{0,j}$ и заканчивающийся в вершине $v_{n,l}$ для некоторых $j,l \leqslant m$.

У кого есть другие варианты понимания условия?

Добавлено спустя 7 минут 58 секунд:

Вот здесь обсуждалась похожая задача. Судя по тому обсуждению, этот вид задач довольно сложен. Вполне возможно, что ответ к этой задаче нельзя представить в виде формулы. Хотя, конечно, можно придумать довольно быстрый (не полнопереборный) алгоритм, запрограммировав который, можно будет на компьютере довольно быстро вычислять искомую вероятность при достаточно больших $n$ и $m$.

[незваный гость]

Можно попытаться поиграть с двойственной задачей: построить сетку, соединяющие центры клеток. Тогда вероятность пути в двойственной задаче = 1 - вероятность в прямой. А если размеры совпадут, то нам повезло!

[maxal]

незваный гость писал(а):

:evil:
Можно попытаться поиграть с двойственной задачей: построить сетку, соединяющие центры клеток. Тогда вероятность пути в двойственной задаче = 1 - вероятность в прямой. А если размеры совпадут, то нам повезло!

Из двойственности следует, что $p_{m,n}=1-p_{n-1,m+1}$. Поэтому "повезет" только в случае $m=n-1$:

$$p_{n-1,n}=\frac{1}{2}.$$

Добавлено спустя 29 минут 30 секунд:

Профессор Снэйп писал(а):

Вот здесь обсуждалась похожая задача. Судя по тому обсуждению, этот вид задач довольно сложен. Вполне возможно, что ответ к этой задаче нельзя представить в виде формулы.

Для полного графа задача как раз-таки должна быть проще. Вот тут мы уже много чего накопали. Да и не выглядит эта задача такой уж сложной. По моим оценкам подумать часик-другой - и будет формула

[Someone]

А ещё существует какая-то "теория протекания"...

[ИСН]

Someone писал(а):

А ещё существует какая-то "теория протекания"...

Вот мне сначала показалось, что задача на "percolation threshold", который для квадратной решётки как раз 1/2. (То есть будь в условии числа чуть побольше 0.5, это была бы почти верная единица, а меньше - почти верный ноль.)
Но задача всё-таки не о том.

[Архипов]

Render писал(а):

Есть мост через реку. Он сложен из одинаковых перекладин в виде сетки m*n. То есть на каждом берегу лежит по m+1 концов.
После штурма каждая перекладина уцелела с вероятностью 0.5. Найти вероятность, что остался путь через реку по мосту.

Что такое "штурм"? Что является условием существования пути? Существование хотя бы одной перекладины с берега на берег?
Почему ("m+1")концов, если их дано (m)? Как влияют поперечные перекладины (n) на существование пути? В условии нет ограничений на m,n (если взять бесконечности, то задача теряет смысл).
Итог: вопросы заняли больше места, чем сама задача.

[Brukvalub]

Архипов писал(а):

Почему ("m+1")концов, если их дано (m)?

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

Архипов писал(а):

Что такое "штурм"?

Это процесс случайного разрушения границ ячеек.

Архипов писал(а):

Как влияют поперечные перекладины (n) на существование пути?

По ним можно переходить от одной продольной границы на другую.

Архипов писал(а):

В условии нет ограничений на m,n (если взять бесконечности, то задача теряет смысл).

Именно поэтому больше никто таких умных вопросов и не задал - все и так это понимают, без дополнительных обсуждений.

Архипов писал(а):

Итог: вопросы заняли больше места, чем сама задача.

Так бывает, особенно если человеку нравиться прикидываться.

[Архипов]

Brukvalub писал(а):

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

Вопросов больше нет. Понятно, что люди придумывают задачу. Пока не закончили. Когда закончат - объявят.

[Render]

Пытался свести к рекурсии - не вышло.
Пытался решить задачу для мостика 1*2 - тоже не получилось.

[Brukvalub]

Render писал(а):

Пытался решить задачу для мостика 1*2 - тоже не получилось.

Странно. Для такого случая все пространство исходов тривиально выписывается, после чего остаётся просто отобрать нужные исходы и подсчитать их вероятности.

[Render]

Brukvalub писал(а):

Render писал(а):

Пытался решить задачу для мостика 1*2 - тоже не получилось.

Странно. Для такого случая все пространство исходов тривиально выписывается, после чего остаётся просто отобрать нужные исходы и подсчитать их вероятности.

Я имел ввиду не перебором, а как-то формулами.

[maxal]

Профессор Снэйп писал(а):

Вот здесь обсуждалась похожая задача. Судя по тому обсуждению, этот вид задач довольно сложен. Вполне возможно, что ответ к этой задаче нельзя представить в виде формулы.

maxal писал(а):

Для полного графа задача как раз-таки должна быть проще. Вот тут мы уже много чего накопали. Да и не выглядит эта задача такой уж сложной. По моим оценкам подумать часик-другой - и будет формула

В общем, дописал я там всякие производящие функции для этой задачи на полном графе. Можно браться за сеточный граф.

Добавлено спустя 22 минуты 49 секунд:

Render писал(а):

Пытался решить задачу для мостика 1*2 - тоже не получилось.

Как уже было сказано выше, для мостика $1\times 2$ да вообще любого мостика размера $(n-1)\times n$ искомая вероятность равна $\frac{1}{2}$.

[Профессор Снэйп]

Архипов писал(а):

Render писал(а):

Есть мост через реку. Он сложен из одинаковых перекладин в виде сетки m*n. То есть на каждом берегу лежит по m+1 концов.
После штурма каждая перекладина уцелела с вероятностью 0.5. Найти вероятность, что остался путь через реку по мосту.

Что такое "штурм"? Что является условием существования пути? Существование хотя бы одной перекладины с берега на берег?
Почему ("m+1")концов, если их дано (m)? Как влияют поперечные перекладины (n) на существование пути? В условии нет ограничений на m,n (если взять бесконечности, то задача теряет смысл).
Итог: вопросы заняли больше места, чем сама задача.

Обратите внимание: я во втором сообщении переформулировал задачу на математическом языке, безо всякий двусмысленностей. Судя по тому, что автор не вмешался и не внёс поправки, задачу следует решать именно в этой формулировке.

[Руст]

Можно не расматривать рёбра при i=0 и i=n (они ни как не влияют), что несколько уменьшает вероятностное пространство. Соответственно остаются n(m+1) перил поперёк реки и (n-1)m перил вдоль реки. Соответственно, искомая вероятность $P=2^{m-n-2mn}N$, где N количество подграфов, соединяющих два берега. Пусть $L_1,L_2,...,L_M$ все пути соединяющие два берега. Тогда N - количество подграфов, содержащих хотя бы один из этих путей и может быть подсчитан как

$$\sum_i N_i-\sum_{i<j}N_{i,j}+\sum_{i<j<k}N_{ijk}-...$$

,
где $N_{i_1i_2,...,i_k}$ количество подграфов содержащих все пути $L_{i_1},L_{i_2},...,L_{i_k}$.
Думаю,что аналитическую формулу несложно получить только при m=1 или n=1.