解説

方針・初手

赤い線分だけからなるグラフで、点 $A$ から点 $E$ への最短距離を考える。

点 $A$ から点 $E$ への長さ $2$ の経路は

$$ A \to B \to E,\qquad A \to F \to E

$$

の2通りである。長さ $2$ の経路がなければ、残る可能性のある最短経路は

$$ A \to B \to C \to D \to E

$$

の長さ $4$ の経路である。

したがって、まず $X=2$ を求め、次に「長さ $2$ の経路はないが長さ $4$ の経路はある」場合を数える。

解法1

各線分が赤である確率は独立に $\dfrac{1}{2}$ である。

長さ $2$ の経路は

$$ A \to B \to E

$$

と

$$ A \to F \to E

$$

の2通りである。

経路 $A \to B \to E$ がすべて赤である確率は

$$ \frac{1}{2}\cdot \frac{1}{2}=\frac{1}{4}

$$

である。同様に、経路 $A \to F \to E$ がすべて赤である確率も $\dfrac{1}{4}$ である。

この2つの経路は使う線分が互いに異なるので、どちらも存在しない確率は

$$ \left(1-\frac{1}{4}\right)^2=\left(\frac{3}{4}\right)^2=\frac{9}{16}

$$

である。よって、少なくとも一方の長さ $2$ の経路が存在する確率は

$$ 1-\frac{9}{16}=\frac{7}{16}

$$

である。したがって

$$ P(X=2)=\frac{7}{16}

$$

である。

次に $X=4$ となる場合を考える。長さ $4$ の経路は

$$ A \to B \to C \to D \to E

$$

である。この経路が赤であるためには、線分 $AB,BC,CD,DE$ がすべて赤でなければならない。

さらに、最短距離が $2$ になってはいけない。$AB$ はすでに赤なので、経路 $A \to B \to E$ を防ぐには $BE$ が黒でなければならない。

また、経路 $A \to F \to E$ も存在してはいけないので、$AF,FE$ がともに赤でないことが必要である。$AF,FE$ がともに赤となる確率は $\dfrac{1}{4}$ だから、ともに赤でない確率は

$$ 1-\frac{1}{4}=\frac{3}{4}

$$

である。

したがって

$$ \begin{aligned} P(X=4) &= \left(\frac{1}{2}\right)^4 \cdot \frac{1}{2} \cdot \frac{3}{4} &= \frac{3}{128} \end{aligned} $$

である。

最後に、$X=0$ とは、点 $A$ から点 $E$ へ赤い線分だけで到達できる経路が存在しない場合である。

この問題では、$A$ から $E$ への最短距離としてあり得る値は $2,4$ のみである。よって

$$ \begin{aligned} P(X=0) &= 1-P(X=2)-P(X=4) \end{aligned} $$

である。

したがって

$$ \begin{aligned} P(X=0) &= 1-\frac{7}{16}-\frac{3}{128} \\ \frac{128}{128}-\frac{56}{128}-\frac{3}{128} \\ \frac{69}{128} \end{aligned} $$

である。

解説

この問題では、すべての赤い辺の組合せを直接数えるよりも、点 $A$ から点 $E$ への経路の形を先に整理するのが有効である。

点 $A$ から点 $E$ への長さ $2$ の経路は左の正方形を通る2通りである。これが1つでも存在すれば、最短距離は必ず $2$ になる。

長さ $2$ の経路がない場合、点 $A$ から点 $E$ に行くためには右側を回る

$$ A \to B \to C \to D \to E

$$

しかない。このため、$X=4$ の条件では、単にこの4本が赤であるだけでなく、長さ $2$ の経路を消す条件も同時に入れる必要がある。

特に、$AB$ が赤である状況では、$A \to B \to E$ を防ぐために $BE$ が黒でなければならない点が重要である。

答え

$$ P(X=0)=\frac{69}{128}

$$

$$ P(X=2)=\frac{7}{16}

$$

$$ P(X=4)=\frac{3}{128}

$$