解説

方針・初手

都市 $A$ から出発しているので、最初から $A$ は訪問済みである。

$k$ 回目の移動で初めて $4$ 都市すべてを訪れるには、$k-1$ 回目の移動終了時点でちょうど $3$ 都市を訪れており、$k$ 回目に残り $1$ 都市へ移動すればよい。

したがって、長さ $k$ の移動経路を数え上げる。

解法1

各回の移動では、直前と異なる $3$ 都市のうち $1$ つを等確率で選ぶ。よって、$k$ 回移動する経路の総数は

$$ 3^k

$$

である。

$k$ 回目で初めて全都市を訪れるとする。このとき、$k-1$ 回目までに訪れていない都市は、出発地 $A$ ではありえない。したがって、$k$ 回目に初めて訪れる都市は $B,C,D$ のいずれかであり、その選び方は $3$ 通りである。

この最後に訪れる都市を $D$ と固定して考える。このとき、$k-1$ 回目までの移動では、都市 $A,B,C$ のみを使い、しかも $B,C$ の両方を少なくとも一度は訪れていなければならない。

都市 $A,B,C$ の中だけで、連続して同じ都市に行かないように $k-1$ 回移動する経路を数える。出発は $A$ であり、各回の移動先は直前の都市以外の $2$ 通りなので、その総数は

$$ 2^{k-1}

$$

である。

ただし、この中には $B,C$ のうち片方しか訪れない経路が含まれている。例えば $B$ を訪れずに $A,C$ だけを使う場合、経路は

$$ A \to C \to A \to C \to \cdots

$$

と一意に決まる。同様に、$C$ を訪れずに $A,B$ だけを使う場合も一意に決まる。

したがって、$B,C$ の両方を訪れる経路数は

$$ 2^{k-1}-2

$$

である。

最後に訪れる都市の選び方が $3$ 通りあるので、条件を満たす経路数は

$$ 3\left(2^{k-1}-2\right)

$$

である。

よって求める確率は

$$ \begin{aligned} \frac{3\left(2^{k-1}-2\right)}{3^k} &= \frac{2^{k-1}-2}{3^{k-1}} \end{aligned} $$

となる。

解説

この問題では、「すべての都市を訪れる」が $k$ 回目に初めて成立するという条件を、$k-1$ 回目終了時点で「ちょうど $3$ 都市を訪れている」と言い換えるのが重要である。

出発地 $A$ は最初から訪問済みなので、最後に初めて訪れる都市は必ず $B,C,D$ のどれかである。また、連続して同じ都市には行けないため、固定した $3$ 都市内での経路数は各回 $2$ 通りずつ選べることから $2^{k-1}$ と数えられる。

ただし、$k-1$ 回目までに固定した $3$ 都市すべてを訪れている必要があるため、片方の都市をまったく訪れない $2$ 通りを除く。この除外を忘れると、まだ $2$ 都市しか訪れていない経路まで数えてしまう。

答え

$$ \boxed{\frac{2^{k-1}-2}{3^{k-1}}}

$$