下図の三角柱ABC-DEFにおいて、Aを始点として、辺に沿って頂点を
回移動する。すなわち
\begin{equation}
\mathrm{P_0 \to P_1 \to P_2 \to \cdots \to} \mathrm{P}_{n -1} \to \mathrm{P}_n \quad (\mbox{ただし} \mathrm{P_0 = A})
\end{equation}において、ほすべて辺であるとする。また、同じ頂点を何度通ってもよいものとする。このような移動経路で、終点
がA, B, Cのいずれかとなるものの総数
を求めよ。
解答例
がD, E, Fのいずれかとなるものの総数を
とします。
例えば、AにはB, C, Dより、DにはA, E, Fより移動してきます。
したがって
\begin{eqnarray}
a_{n +1} &=& 2a_n +b_n \tag{1} \\
b_{n +1} &=& a_n +2b_n \tag{2}
\end{eqnarray}が成り立ちます。また
\begin{eqnarray}
a_0 &=& 1 \tag{3} \\
b_0 &=& 0 \tag{4}
\end{eqnarray}です。
式(1), (2)より
\begin{eqnarray}
a_{n +1} -b_{n +1} &=& a_n -b_n \tag{5} \\
a_{n +1} +b_{n +1} &=& 3(a_n +b_n) \tag{6}
\end{eqnarray}となります。
式(3)～(6)より、
\begin{eqnarray}
a_n -b_n &=& a_0 -b_0 &=& 1 \tag{7} \\
a_n +b_n &=& 3^n (a_0 +b_0) &=& 3^n \tag{8}
\end{eqnarray}を得ます。
式(7), (8)より、求める総数は
\begin{equation}
a_n = \frac{3^n +1}{2}
\end{equation}となります。
解説
直接求める術が見当たらないので、漸化式を組むことになります。
その際、ABCだけでなくDEFの方も考えると上手いこといきます。
漸化式を組めれば、後は容易です。
こういう問題が京大で出るのは意外です。
