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

図のカードの隣接関係は、中心 C から4方向にそれぞれ長さ2の枝が伸びた形である。偶数秒後には C または外端 A,E,F,I にいる。対称性より、任意の外端 L について $N(C,L,2n)=N(C,E,2n)$ とおける。$\quad s_n=N(C,C,2n),\quad p_n=N(C,E,2n)$ とする。2秒の移動では、C から C へ戻る経路は4通り、C から各外端へは1通りである。また外端からは、同じ外端へ戻る経路と 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\geq1$ について $$N(C,E,2n)=p_n=5^{n-1}.$$$\quad$ 次に $q_n=N(A,E,2n)$ とする。2n 秒後のカードからさらに2秒で E に着くには、現在 C か E にいる必要があり、どちらからも E へ行く2秒の経路は1通りである。経路を逆向きにたどる対称性から $N(A,C,2n)=N(C,A,2n)=p_n$ なので $$q_{n+1}=p_n+q_n,\qquad q_1=0.$$ ゆえに $n\geq2$ では $$\displaystyle N(A,E,2n)=q_n=\sum\limits _{k=1}^{n-1}p_k =1+5+\cdots+5^{n-2} =\frac{5^{n-1}-1}{4}.$$