条件を満たす直角三角形の辺の長さを $a-d,$ $a,$ $a+d$ $(a > d > 0)$ とおく. このとき, 三平方の定理により \[\begin{aligned} (a-d)^2+a^2 &= (a+d)^2 \\ a^2-2ad+d^2+a^2 &= a^2+2ad+d^2 \\ a^2 &= 4ad \end{aligned}\] が成り立つから, 両辺を $a\,(> 0)$ で割ると \[ a = 4d\] となる. ゆえに, 条件を満たす直角三角形の $3$ 辺の長さの比は \[ (a-d):a:(a+d) = 3d:4d:5d = 3:4:5\] である.

(1)

$1$ 本の棒の最も上にある $n$ 枚を別の棒の最も上に移すときの手数の最小値を $a_n$ とおく. 棒 A の最も上にある $n+1$ 枚を棒 B の最も上に移すためには, まず上の $n$ 枚を棒 C に移し, 次に棒 A に残された $1$ 枚を棒 B に移し, 最後に棒 C に移された $n$ 枚を棒 B に移す必要がある. よって, \[ a_{n+1} = a_n+1+a_n = 2a_n+1 \quad \cdots [1]\] が成り立つ.

\[ \alpha = 2\alpha +1 \quad \cdots [2]\] を解くと $\alpha = -1$ となるので, $[1]-[2]$ から

$a_{n+1}-\alpha = 2(a_n-\alpha )$　つまり　$a_{n+1}+1 = 2(a_n+1)$

となる. $\{ a_n+1\}$ は初項 $a_1+1 = 1+1 = 2,$ 公比 $2$ の等比数列であるから,

$a_n+1 = 2^n$　つまり　$a_n = 2^n-1$

である.

(2)

棒 A の最も上にある $n$ 枚のうち, 白色の円盤を棒 B, 黒色の円盤を棒 C に移す (以下, 色ごとに分けるという) 手数の最小値を $b_n$ とおく. 棒 A の $n+3$ 枚を色ごとに分けるためには, まず上の $n+2$ 枚を棒 C に移してから残りの $1$ 枚を棒 B に移し, 次に棒 C に移された $n+2$ 枚のうち $n$ 枚を棒 A に移してから残りの $2$ 枚のうち上の $1$ 枚のみを棒 B に移し (下の $1$ 枚は動かす必要はない), 最後に棒 A に戻された $n$ 枚を色ごとに分ける必要がある. よって, \[ b_{n+3} = a_{n+2}+1+a_n+1+b_n\] が成り立つから, (1) とあわせると \[ b_{n+3}-b_n = 2^{n+2}+2^n = 5\cdot 2^n\] が得られる. また, 明らかに \[ b_1 = 1, \quad b_2 = 2, \quad b_3 = 5\] である.

(i)

$n = 3q$ ($q$: 正の整数) のとき. $q \geqq 2$ のとき \[\begin{aligned} b_n &= b_3+\sum_{k = 1}^{q-1}(b_{3k+3}-b_{3k}) \\ &= 5+\sum_{k = 1}^{q-1}5\cdot 2^{3k} = \sum_{k = 0}^{q-1}5\cdot 8^k \\ &= 5\cdot\frac{8^q-1}{8-1} = \frac{5\cdot 2^{3q}-5}{7} = \frac{5\cdot 2^n-5}{7} \end{aligned}\] であり, これは $q = 1$ のときも成り立つ.

(ii)

$n = 3q-2$ ($q$: 正の整数) のとき. $q \geqq 2$ のとき \[\begin{aligned} b_n &= b_1+\sum_{k = 1}^{q-1}(b_{3k+1}-b_{3k-2}) \\ &= 1+\sum_{k = 1}^{q-1}5\cdot 2^{3k-2} = 1+\sum_{k = 1}^{q-1}10\cdot 8^{k-1} \\ &= 1+10\cdot\frac{8^{q-1}-1}{8-1} = \frac{5\cdot 2^{3q-2}-3}{7} = \frac{5\cdot 2^n-3}{3} \end{aligned}\] であり, これは $q = 1$ のときも成り立つ.

(iii)

$n = 3q-1$ ($q$: 正の整数) のとき. $q \geqq 2$ のとき \[\begin{aligned} b_n &= b_2+\sum_{k = 1}^{q-1}(b_{3k+2}-b_{3k-1}) \\ &= 2+\sum_{k = 1}^{q-1}5\cdot 2^{3k-1} = 2+\sum_{k = 1}^{q-1}20\cdot 8^{k-1} \\ &= 2+20\cdot\frac{8^{q-1}-1}{8-1} = \frac{5\cdot 2^{3q-1}-6}{7} = \frac{5\cdot 2^n-6}{3} \end{aligned}\] であり, これは $q = 1$ のときも成り立つ.

(3)

$1$ 本の棒の最も上にある $n$ 枚のうち, 一番下の $1$ 枚を動かさずに, 白色の円盤を棒 A, 灰色の円盤を棒 B, 黒色の円盤を棒 C に移す (以下, 色ごとに移すという) 手数の最小値を $c_n$ とおく. 棒 A の $n+2$ 枚を色ごとに移すためには, まず上の $n$ 枚を棒 C に移してから残りの $1$ 枚を棒 B に移し, 最後に棒 C に移された $n$ 枚を色ごとに移す必要がある. よって, \[ c_{n+2} = a_n+1+c_n\] が成り立つから, (1) とあわせると \[ c_{n+2}-c_n = 2^n\] が得られる. また, 明らかに \[ c_1 = 0, \quad c_2 = 1\] である.

(i)

$n = 2q$ ($q$: 正の整数) のとき. $q \geqq 2$ のとき \[\begin{aligned} c_n &= c_2+\sum_{k = 1}^{q-1}(c_{2k+2}-c_{2k}) \\ &= 1+\sum_{k = 1}^{q-1}2^{2k} = \sum_{k = 0}^{q-1}4^k \\ &= \frac{4^q-1}{4-1} = \frac{2^{2q}-1}{3} = \frac{2^n-1}{3} \end{aligned}\] であり, これは $q = 1$ のときも成り立つ.

(ii)

$n = 2q-1$ ($q$: 正の整数) のとき. $q \geqq 2$ のとき \[\begin{aligned} c_n &= c_1+\sum_{k = 1}^{q-1}(c_{2k+1}-c_{2k-1}) \\ &= \sum_{k = 1}^{q-1}2^{2k-1} = \sum_{k = 1}^{q-1}2\cdot 4^{k-1} \\ &= 2\cdot\frac{4^{q-1}-1}{4-1} = \frac{2^{2q-1}-2}{3} = \frac{2^n-2}{3} \end{aligned}\] であり, これは $q = 1$ のときも成り立つ.

　畳をすべて縦に敷いたとき縦に $1$ 枚, 横に $n$ 枚の畳が敷けるようなうなぎの寝床において, 畳の敷き方の総数を $a_n$ とおく.

(1)

まず, 数列 $\{ a_n\}$ が満たす漸化式を求める. $n > 2$ のとき, 最後に敷く畳の向きに着目すると, 次の $2$ つの場合が考えられる.

(i)

最後に畳を横に敷く場合. $n$ 枚の畳を敷く方法は, $n-2$ 枚の畳の敷き方 $a_{n-2}$ 通りだけある.

(ii)

最後に畳を縦に敷く場合. $n$ 枚の畳を敷く方法は, $n-1$ 枚の畳の敷き方 $a_{n-1}$ 通りだけある.

(i), (ii) は同時に起こらないから, \[ a_n = a_{n-2}+a_{n-1} \quad (n > 2)\] つまり \[ a_{n+2} = a_n+a_{n+1} \quad \cdots [1]\] が成り立つ.

(2)

次に, 数列 $\{ a_{n+1}-\alpha a_n\},$ $\{ a_{n+1}-\beta a_n\}$ がそれぞれ公比 $\beta,$ $\alpha$ の等比数列になるような定数 $\alpha,$ $\beta\ (\alpha > \beta )$ を求める. このとき, \[\begin{aligned} a_{n+2}-\alpha a_{n+1} &= \beta (a_{n+1}-\alpha a_n), \\ a_{n+2}-\beta a_{n+1} &= \alpha (a_{n+1}-\beta a_n) \end{aligned}\] から \[ a_{n+2} = (\alpha +\beta )a_{n+1}-\alpha\beta a_n \quad \cdots [2]\] が成り立つ. $[1],$ $[2]$ から, \[\alpha +\beta = 1,\quad \alpha\beta = -1\] が成り立てばよい. このとき, $\alpha,$ $\beta$ は $2$ 次方程式 $x^2-x-1 = 0$ の解であるから, 条件を満たす $\alpha,$ $\beta$ の組として \[ (\alpha,\beta ) = \left(\frac{1+\sqrt 5}{2},\frac{1-\sqrt 5}{2}\right)\] がとれる.

(3)

最後に, 数列 $\{ a_n\}$ の一般項を求める. $a_1 = 1,$ $a_2 = 2$ である. よって, 数列 $\{ a_{n+1}-\alpha a_n\},$ $\{ a_{n+1}-\beta a_n\}$ の初項は, それぞれ \[\begin{aligned} a_2-\alpha a_1 = 2-\alpha &= \frac{3-\sqrt 5}{2} = \beta ^2, \\ a_2-\beta a_1 = 2-\beta &= \frac{3+\sqrt 5}{2} = \alpha ^2 \end{aligned}\] である. したがって, $\alpha,$ $\beta$ のとり方から, \[\begin{aligned} a_{n+1}-\alpha a_n &= \beta ^{n+1}, \\ a_{n+1}-\beta a_n &= \alpha ^{n+1} \end{aligned}\] が成り立つ. 辺々を引くと \[ (\alpha -\beta )a_n = \alpha ^{n+1}-\beta ^{n+1}\] となるので, $\alpha -\beta = \sqrt 5$ から \[ a_n = \frac{1}{\sqrt 5}\left\{\left(\frac{1+\sqrt 5}{2}\right) ^{n+1}-\left(\frac{1-\sqrt 5}{2}\right) ^{n+1}\right\}\] が成り立つ.

(1)

まず, それぞれが動かないか隣に移るように $1$ 列に並んだ $n$ 人を並べ替える方法の総数 $a_n$ を求める.

(i)

最後尾の人が隣に移る場合. $n$ 人を並べ替える方法は, $n-2$ 人の並べ方 $a_{n-2}$ 通りだけある.

(ii)

最後尾の人が動かない場合. $n$ 人を並べ替える方法は, $n-1$ 人の並べ方 $a_{n-1}$ 通りだけある.

(i), (ii) は同時に起こらないから, \[ a_n = a_{n-2}+a_{n-1} \quad (n > 2)\] が成り立つ. また, $a_1 = 1,$ $a_2 = 2$ であるから, $\{ a_n\}$ は前問の数列に等しく, その一般項は \[ a_n = \frac{\alpha ^{n+1}-\beta ^{n+1}}{\sqrt 5} \quad \left(\alpha = \frac{1+\sqrt 5}{2},\ \beta = \frac{1-\sqrt 5}{2}\right)\] である.

(2)

$n$ 人の列の先頭と最後尾をつなげて, $n$ 人を円形に並べる. 求める場合の数を $L_n$ とおく.

(i)

先頭と最後尾の人が入れ替わる場合. $n$ 人を並べ替える方法は, 列における $n-2$ 人の並べ方 $a_{n-2}$ 通りだけある.

(ii)

先頭と最後尾の人が入れ替わらない場合. $n$ 人を並べ替える方法は, 列における $n$ 人の並べ方 $a_n$ 通りだけある.

(i), (ii) は同時に起こらないから, \[\begin{aligned} L_n &= a_{n-2}+a_n \\ &= \frac{\alpha ^{n-1}-\beta ^{n-1}}{\sqrt 5}+\frac{\alpha ^{n+1}-\beta ^{n+1}}{\sqrt 5} \\ &= \frac{\alpha ^{n-1}}{\sqrt 5}(1+\alpha ^2)-\frac{\beta ^{n-1}}{\sqrt 5}(1+\beta ^2) \\ &= \frac{\alpha ^{n-1}}{\sqrt 5}\cdot\sqrt 5\alpha -\frac{\beta ^{n-1}}{\sqrt 5}\cdot (-\sqrt 5\beta ) \\ &= \left(\frac{1+\sqrt 5}{2}\right) ^n+\left(\frac{1-\sqrt 5}{2}\right) ^n \end{aligned}\] が成り立つ. ここで, $\alpha ^2-\alpha -1 = 0,$ $\beta ^2-\beta -1 = 0$ から \[\begin{aligned} 1+\alpha ^2 &= \alpha +2 = \frac{1+\sqrt 5}{2}+2 = \frac{5+\sqrt 5}{2} = \sqrt 5\alpha, \\ 1+\beta ^2 &= \beta +2 = \frac{1-\sqrt 5}{2}+2 = \frac{5-\sqrt 5}{2} = -\sqrt 5\beta \end{aligned}\] であることを使った.

　アリが $n$ 秒後に頂点 $\mathrm A,$ $\mathrm B,$ $\mathrm C,$ $\mathrm D$ にいる確率をそれぞれ $a_n,$ $b_n,$ $c_n,$ $d_n$ とおく. このとき, \[\begin{aligned} &a_{n+1} = \frac{1}{3}b_n+\frac{1}{3}c_n+\frac{1}{3}d_n, \\ &a_n+b_n+c_n+d_n = 1 \end{aligned}\] であるから, が成り立つ. 両辺から $\alpha = -\dfrac{1}{3}\alpha +\dfrac{1}{3}$ の解 $\alpha = \dfrac{1}{4}$ を引いて整理すると, \[ a_{n+1}-\frac{1}{4} = -\frac{1}{3}\left( a_n-\frac{1}{4}\right)\] が得られる. よって, $\left\{ a_n-\dfrac{1}{4}\right\}$ は第 $0$ 項 $a_0-\dfrac{1}{4} = 1-\dfrac{1}{4} = \dfrac{3}{4},$ 公比 $-\dfrac{1}{3}$ の等比数列であるから, である.

　最後に残った生徒の出席番号を $f(n)$ とおく. 数値実験として, $1 \leqq n \leqq 30$ における $f(n)$ の値を求めると, 次のようになる. 　表をよく観察すると, $n = 2^m+r$ ($m$: 非負整数, $0 \leqq r < 2^m$) のとき \[ f(n) = 2r+1 \quad \cdots [*]\] が成り立つと予想できるから, $n$ に関する数学帰納法でこれを示す.

(1)

証明に用いる数列 $\{ f(n)\}$ の漸化式を求める. 番号の偶奇に着目すると, $f(1) = 1$ から \[\begin{aligned} f(2) &= 1 = 2f(1)-1, & f(3) &= 3 = 2f(1)+1, \\ f(4) &= 1 = 2f(2)-1, & f(5) &= 3 = 2f(2)+1, \\ f(6) &= 5 = 2f(3)-1, & f(7) &= 7 = 2f(3)+1 \end{aligned}\] となり, \[ f(2n) = 2f(n)-1, \quad f(2n+1) = 2f(n)+1\] が成り立つと予想できるから, これを示す.

• 生徒が $2n$ 人の場合. $n$ 人が輪から抜けたとき, 出席番号が \[ 1,\ \cdots,\ 2k-1,\ \cdots,\ 2n-1\] の $n$ 人の生徒が残っている. 最後の $1$ 人になるまで操作を続けると, このうちの $f(n)$ 番目の生徒が最後に残るから, その生徒の出席番号は \[ f(2n) = 2f(n)-1\] である.
• 生徒が $2n+1$ 人の場合. $n+1$ 人が輪から抜けたとき, 出席番号が \[ 3,\ \cdots,\ 2k+1,\ \cdots,\ 2n+1\] の $n$ 人の生徒が残っている. 最後の $1$ 人になるまで操作を続けると, このうちの $f(n)$ 番目の生徒が最後に残るから, その生徒の出席番号は \[ f(2n+1) = 2f(n)+1\] である.

(2)

上記の予想を示す.

(i)

$f(1) = 1 = 2\cdot 0+1$ であるから, $n = 1$ のとき $[*]$ が成り立つ.

(ii)

$n > 1$ として, $n$ 未満のすべての正の整数に対して $[*]$ が成り立つとする.

• $n$ が偶数の場合. $r$ は偶数であり, \[\frac{n}{2} = 2^{m-1}+\frac{r}{2}\] であるから, \[\begin{aligned} f(n) &= f\left( 2\cdot\frac{n}{2}\right) \\ &= 2f\left(\frac{n}{2}\right) -1 \quad (\because (1)) \\ &= 2\left( 2\cdot\frac{r}{2}+1\right) -1 = 2r+1 \end{aligned}\] が成り立つ.
• $n$ が偶数の場合. $r$ は奇数であり, \[\frac{n-1}{2} = 2^{m-1}+\frac{r-1}{2}\] であるから, \[\begin{aligned} f(n) &= f\left( 2\cdot\frac{n-1}{2}+1\right) \\ &= 2f\left(\frac{n-1}{2}\right) +1 \quad (\because (1)) \\ &= 2\left( 2\cdot\frac{r-1}{2}+1\right) +1 = 2r+1 \end{aligned}\] が成り立つ.

(i), (ii) から, すべての正の整数 $n$ に対して $[*]$ が成り立つ.