本格数学クイズ (数列)
数列
クイズ《ハノイの塔》
地面に $3$ 本の棒 A, B, C が立てられており, 棒 A に穴の開いた半径の異なる $n$ 枚の円盤が半径の大きい順に通されている.
- (1)
- すべての円盤を棒 B に移す手数の最小値はいくらか.
- (2)
- 円盤に半径の大きい方から $2$ 枚ごとに白色, 黒色の順に色が塗られているとする. 白色の円盤を棒 B, 黒色の円盤を棒 C に移す手数の最小値はいくらか.
- (3)
- 円盤に半径の大きい方から $3$ 枚ごとに白色, 灰色, 黒色の順に色が塗られているとする. 白色の円盤を棒 A, 灰色の円盤を棒 B, 黒色の円盤を棒 C に移す手数の最小値はいくらか.
(有名問題)
答え
- (1)
- $2^n-1.$
- (2)
- $n$ が $3$ の倍数のとき $\dfrac{5\cdot 2^n-5}{7},$ $n$ を $3$ で割った余りが $1$ のとき $\dfrac{5\cdot 2^n-3}{7},$ $n$ を $3$ で割った余りが $2$ のとき $\dfrac{5\cdot 2^n-6}{7}.$
- (3)
- $n$ が偶数のとき $\dfrac{2^n-1}{3},$ $n$ が奇数のとき $\dfrac{2^n-2}{3}.$
解説
- (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\}$ は初項 $a_1+1 = 1+1 = 2,$ 公比 $2$ の等比数列であるから,$a_{n+1}-\alpha = 2(a_n-\alpha )$ つまり $a_{n+1}+1 = 2(a_n+1)$
である.$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$ のときも成り立つ.
クイズ《うなぎの寝床での畳の敷き方》
ちょうど $n$ 枚の畳が敷けるような長方形のうなぎの寝床に畳を敷く方法は何通りあるか.
ただし, 寝床の縦の長さは畳の長い方の辺の長さに等しく, 横の長さは畳の短い方の辺の長さの $n$ 倍に等しいとする.
(有名問題)
答え
$\displaystyle\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$ 枚, 横に $n$ 枚の畳が敷けるようなうなぎの寝床において, 畳の敷き方の総数を $a_n$ とおく.
- (1)
- まず, 数列 $\{ a_n\}$ が満たす漸化式を求める.
$n > 2$ のとき, 最後に敷く畳の向きに着目すると, 次の $2$ つの場合が考えられる.
- (i)
- 最後に畳を横に敷く場合. $n$ 枚の畳を敷く方法は, $n-2$ 枚の畳の敷き方 $a_{n-2}$ 通りだけある.
- (ii)
- 最後に畳を縦に敷く場合. $n$ 枚の畳を敷く方法は, $n-1$ 枚の畳の敷き方 $a_{n-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\}\] が成り立つ.
参考
- 数列 $\{ a_n\}$ は「フィボナッチ数列」$\{ F_n\}$ の第 $2$ 項以降を順に並べて得られる数列である. つまり, $a_n = F_{n+1}$ である.
- 初期条件 $F_1 = F_2 = 1$ と漸化式 $F_{n+2} = F_n+F_{n+1}$ で定まる数列 \[\{ F_n\}:1,1,2,3,5,8,13,21,34,55,89,144,\cdots\] を「フィボナッチ数列」(Fibonacci sequence) と呼ぶ. この数列の項は「フィボナッチ数」と呼ばれ, 花びらの枚数, 植物の種が並んでできるらせんの本数など, 自然界でよく見られる整数である.
- 公式 \[ F_n = \frac{1}{\sqrt 5}\left\{\left(\frac{1+\sqrt 5}{2}\right) ^n-\left(\frac{1-\sqrt 5}{2}\right) ^n\right\}\] は「ビネの公式」(Binet's formula) として知られている.
- $n$ 番目の「フィボナッチ数」$F_n$ は $\dfrac{1}{\sqrt 5}\left(\dfrac{1+\sqrt 5}{2}\right) ^n+\dfrac{1}{2}$ の整数部分に等しい. 実際,「ビネの公式」 \[ F_n = \frac{\alpha ^n-\beta ^n}{\sqrt 5}\] と $-1 < \beta < 0,$ $\sqrt 5 > 2$ により \[\left| F_n-\frac{\alpha ^n}{\sqrt 5}\right| = \left| -\frac{\beta ^n}{\sqrt 5}\right| = \frac{|\beta |^n}{\sqrt 5} < \frac{1}{2}\] であるから, \[\begin{aligned} -\frac{1}{2} &< F_n-\frac{\alpha ^n}{\sqrt 5} < \frac{1}{2} \\ \left(\frac{\alpha ^n}{\sqrt 5}+\frac{1}{2}\right) -1 = \frac{\alpha ^n}{\sqrt 5}-\frac{1}{2} &< F_n < \frac{\alpha ^n}{\sqrt 5}+\frac{1}{2} \end{aligned}\] が成り立つ. $F_n$ は整数であるから, これは $\dfrac{\alpha ^n}{\sqrt 5}+\dfrac{1}{2}$ の整数部分が $F_n$ に等しいことを意味する.
- 「フィボナッチ数列」の隣り合う項の比は「黄金比」$1:\dfrac{1+\sqrt 5}{2}$ に限りなく近づいていくこともよく知られている (こちらを参照).