解説

方針・初手

終点が $A,B,C$ のいずれかであるか、$D,E,F$ のいずれかであるかだけに注目する。

三角柱では、上の三角形 $ABC$ の各頂点からは、上の三角形内の頂点へ行く辺が $2$ 本、下の対応する頂点へ行く辺が $1$ 本ある。下の三角形 $DEF$ についても同様である。

解法1

$n$ 回移動した後に $A,B,C$ のいずれかにいる移動経路の数を $a_n$、$D,E,F$ のいずれかにいる移動経路の数を $b_n$ とする。

始点は $A$ であるから、

$$ a_0=1,\qquad b_0=0

$$

である。

次に、$a_n,b_n$ の漸化式を立てる。終点が $A,B,C$ のいずれかになるには、直前の頂点が上側にあった場合と下側にあった場合がある。

上側の各頂点から上側へ行く辺は $2$ 本あるので、直前に上側にいる経路からは $2a_{n-1}$ 通りが上側へ移る。

下側の各頂点から上側へ行く辺は対応する垂直方向の辺 $1$ 本だけなので、直前に下側にいる経路からは $b_{n-1}$ 通りが上側へ移る。

したがって、

$$ a_n=2a_{n-1}+b_{n-1}

$$

である。同様に、下側に終わる経路についても

$$ b_n=a_{n-1}+2b_{n-1}

$$

が成り立つ。

ここで、全体の経路数を考える。どの頂点からも進める辺は $3$ 本あるので、$n$ 回移動する経路の総数は

$$ a_n+b_n=3^n

$$

である。

また、2つの漸化式を引くと、

$$ a_n-b_n=(2a_{n-1}+b_{n-1})-(a_{n-1}+2b_{n-1})=a_{n-1}-b_{n-1}

$$

となる。よって、$a_n-b_n$ は一定であり、初期値から

$$ a_n-b_n=a_0-b_0=1

$$

である。

以上より、

$$ \begin{cases} a_n+b_n=3^n,\\ a_n-b_n=1 \end{cases}

$$

を解けばよい。2式を加えて、

$$ 2a_n=3^n+1

$$

となるから、

$$ a_n=\frac{3^n+1}{2}

$$

を得る。

解説

この問題では、終点を個別に $A,B,C,D,E,F$ と追う必要はない。求めるものが「終点が $A,B,C$ のいずれか」となっているため、上側の三角形にいる経路数と下側の三角形にいる経路数だけを追えば十分である。

重要なのは、三角柱の各頂点からは「同じ側へ行く辺が $2$ 本」「反対側へ行く辺が $1$ 本」あるという対称性である。この対称性により、$a_n,b_n$ の2変数の漸化式に落とせる。

また、全経路数が $3^n$ であることと、差 $a_n-b_n$ が初期値のまま保存されることを組み合わせると、直接 $a_n$ が求まる。

答え

$$ a_n=\frac{3^n+1}{2}

$$