1群馬大学 2024年 数学 第1問解答・解説

図のカードの隣接関係を離散的なグラフとして捉え、偶数秒ごとの経路数に漸化式を立てる。C から外端への経路数は等比数列の漸化式で求め、A から E への経路数はその累積和で表す。

(1)

図のカードの隣接関係は、中心 $\mathrm{C}$ から 4 方向にそれぞれ長さ 2 の枝が伸びた形である。偶数秒後には $\mathrm{C}$ または外端 $\mathrm{A}$、$\mathrm{E}$、$\mathrm{F}$、$\mathrm{I}$ にいる。対称性より、任意の外端 $\mathrm{L}$ について $N(\mathrm{C},\mathrm{L},2n)=N(\mathrm{C},\mathrm{E},2n)$ とおける。そこで
$$s_{n}=N(\mathrm{C},\mathrm{C},2n),\qquad p_{n}=N(\mathrm{C},\mathrm{E},2n)$$
とする。2 秒の移動では、$\mathrm{C}$ から $\mathrm{C}$ へ戻る経路は 4 通り、$\mathrm{C}$ から各外端へは 1 通りである。また外端からは、同じ外端へ戻る経路と $\mathrm{C}$ へ行く経路がそれぞれ 1 通りで、他の外端へ行く経路はない。よって
$$s_{0}=1,\quad p_{0}=0,\qquad s_{n+1}=4s_{n}+4p_{n},\quad p_{n+1}=s_{n}+p_{n}.$$
したがって $s_{n+1}=4p_{n+1}$ であり、
$$p_{n+2}=s_{n+1}+p_{n+1}=5p_{n+1}.$$
$p_{1}=1$ だから、$n\geqq1$ について
$$N(\mathrm{C},\mathrm{E},2n)=p_{n}=5^{\,n-1}.$$

(2)

次に $q_{n}=N(\mathrm{A},\mathrm{E},2n)$ とする。$2n$ 秒後のカードからさらに 2 秒で $\mathrm{E}$ に着くには、現在 $\mathrm{C}$ か $\mathrm{E}$ にいる必要があり、どちらからも $\mathrm{E}$ へ行く 2 秒の経路は 1 通りである。経路を逆向きにたどる対称性から $N(\mathrm{A},\mathrm{C},2n)=N(\mathrm{C},\mathrm{A},2n)=p_{n}$ なので
$$q_{n+1}=p_{n}+q_{n},\qquad q_{1}=0.$$
ゆえに $n\geqq2$ では
$$N(\mathrm{A},\mathrm{E},2n)=q_{n}=\sum_{k=1}^{n-1}p_{k}=1+5+\cdots+5^{\,n-2}=\dfrac{5^{\,n-1}-1}{4}.$$