13 座桥随机毁坏：洪水后还能过河概率

Two riverbanks and six islands

专题: Probability / 概率
难度: L4
来源: QuantQuestion

题目详情

Two riverbanks and six islands are connected by thirteen bridges as shown in the picture below.

When a flood occurs, each bridge is destroyed with probability $\frac{1}{2}$ , independent of the others. What is the probability that it will still be possible to cross the river after the flood using the bridges that remain?

解析

把“还能过河”记为事件 $A$ 。

考虑该平面桥图的对偶图：桥被毁相当于对偶边可通行。定义事件 $B$ 为“可以沿河道开一艘高船通过而不需从任何未毁桥下穿过”，它等价于对偶图中存在一条对应的连通路径。

在该平面结构下， $A$ 与 $B$ 互斥且必有其一发生（典型的平面对偶割/路互补关系）。

每座桥独立以 $1/2$ 概率毁坏，使得“原图配置”与“对偶图配置”在分布上对称，因此

\mathbb{P}(A)=\mathbb{P}(B),\qquad \mathbb{P}(A)+\mathbb{P}(B)=1.

于是

\boxed{\mathbb{P}(A)=\frac12}.