問題
6個の点が下図のように長さ1の線分で結ばれているとする．各線分をそれぞれ独立に確率で赤または黒で塗る．赤く塗られた線分だけを通って点から点に至る経路がある場合はそのうちで最短のものの長さをとする．そのような経路がない場合はを0とする．このとき，について，となる確率を求めよ．% 図は省略
方針
図の辺を確認すると、 から への長さ2の経路は と の2本であり、長さ2が存在しない場合に残る長さ4の経路は である。全7辺の赤黒の塗り方は等確率なので、塗り方の個数を数える。まず長さ2の赤経路がある場合を包除原理で数え、次に長さ2がなく長さ4だけがある場合を必要十分条件で数える。最後に余事象で を出す。 別解として、特に は「赤で到達できない」場合を、点 から出る2辺の色で場合分けして直接数える方法も確認する。
解答
図の辺は の7本である。各辺は独立に赤または黒に塗られるので、全ての塗り方は 通りであり、すべて等確率である。
まず の場合を数える。 から への長さ2の経路は の2本である。経路 が赤だけで通れるためには の2本が赤であればよく、残り5本は任意であるから 通りである。同様に、経路 が赤だけで通れる塗り方も32通りである。
ただし、両方の長さ2経路が赤で通れる場合は重複して数えている。この重複は の4本が赤で、残り3本が任意の場合なので 通りである。よって であり である。
次に の場合を数える。長さ2の赤経路が存在せず、かつ赤だけで から に行けるには、図から長さ4の経路 が赤で通れることが必要である。このためには の4本が赤でなければならない。
さらに、長さ2の経路 が赤にならないためには、すでに は赤なので でなければならない。また、長さ2の経路 が赤にならないためには、 の少なくとも一方が黒であればよい。したがって の塗り方は の3通りである。よって であり である。
最後に、赤だけで から へ行く経路がない場合は である。 から へ行ける場合の最短長は、上で数えたように2または4であるから である。したがって であり である。
別解。 は、赤線だけでは から に到達できない場合を直接数えても求められる。点 から出る辺は の2本であるから、この2本の色で分ける。
がともに黒のとき、 からどこにも進めないので、残り5本は任意で 通りである。
が赤、 が黒のとき、 までは到達できる。 に到達しないためには が黒であることが必要十分であり、残り4本は任意で 通りである。
が黒、 が赤のとき、 までは到達できる。 に到達しないためには が黒で、さらに下側の経路 がすべて赤ではないことが必要十分である。辺 の塗り方は、全部赤の1通りを除いた 通りであり、 は任意なので 通りである。
最後に がともに赤のときは、 と まで到達できる。したがって と はともに黒でなければならず、さらに がすべて赤ではない必要がある。よって 通りである。
以上より到達不能な塗り方は 通りであり、 を得る。これは余事象で求めた値と一致する。