トップ› 北海道大学› 2011年› 理系第4問

北海道大学 2011年理系第4問解説

方針・初手

各回の操作において、箱から次の箱へ白玉が移される場合と赤玉が移される場合を区別し、それぞれの総数の関係を漸化式で捉えることが基本方針です。玉にはすべて異なる番号が振られており区別されるため、移動の際には「どの玉を選ぶか」という場合の数を掛け合わせて総数を求めます。$k$ 番目の箱から $k+1$ 番目の箱へ白玉が移される場合の総数を $w_k$、赤玉が移される場合の総数を $r_k$ と定義することで、問題文の $a_n, s_n$ を簡潔に表すことができます。

解法1

$k$ 回目の操作（$k$ 番の箱から $k+1$ 番の箱へ玉を1個移す操作、$1 \le k \le n-1$）において、白玉を移すような再配分の総数を $w_k$、赤玉を移すような再配分の総数を $r_k$ とおく。すべての玉は区別されるため、選び方の総数を考える。

求める $a_n$ は、$n$ 番の箱に最終的に白玉が $q+1$ 個ある、すなわち $n-1$ 回目の操作で白玉が移される再配分の総数であるから、$a_n = w_{n-1}$ である。また、$k$ 回目の操作までを終えた時点での再配分の総数は $w_k + r_k$ であり、とくに $s_n = w_{n-1} + r_{n-1}$ である。

(1) 1回目の操作で 1 番の箱から白玉を選ぶ総数は、最初に入っている $q$ 個の白玉から1つを選ぶので $q$ 通り。よって $w_1 = q$ である。同様に $r_1 = r$ である。 $a_2$ は 1 番の箱から 2 番の箱へ白玉が移される総数なので、

$$ a_2 = w_1 = q $$

$a_3$ は 2 番の箱から 3 番の箱へ白玉が移される総数 $w_2$ である。 1 回目の操作で白玉が移された場合（総数 $w_1$）、2 番の箱には白玉が $q+1$ 個、赤玉が $r$ 個あり、そこから白玉を選ぶ方法は $q+1$ 通り。 1 回目の操作で赤玉が移された場合（総数 $r_1$）、2 番の箱には白玉が $q$ 個、赤玉が $r+1$ 個あり、そこから白玉を選ぶ方法は $q$ 通り。よって、次の関係が成り立つ。

$$ a_3 = w_2 = (q+1)w_1 + q r_1 = (q+1)q + qr = q(q+r+1) $$

(2) $s_n$ は $n-1$ 回の操作のすべての選び方の総数である。 1回目の操作において、1 番の箱からは最初に入っている $q+r$ 個から1個を選ぶため、$q+r$ 通りである。 $k$ 回目の操作（$2 \le k \le n-1$）において、$k$ 番の箱には最初から入っている $q+r$ 個に、前の箱から移された1個を加えた計 $q+r+1$ 個の玉が入っている。移された玉の色に関わらず、箱の中の玉の総数は常に $q+r+1$ 個であるため、ここから1個を選ぶ方法は常に $q+r+1$ 通りである。よって、$1$ 回目の操作と残り $n-2$ 回の操作の選択肢の数を掛け合わせて、

$$ s_n = (q+r)(q+r+1)^{n-2} $$

(3) (1)の $w_2$ の導出と同様に考えて、$k \ge 2$ において $k$ 番の箱から $k+1$ 番の箱へ白玉が移される総数 $w_k$ は、次のように表される。

$$ w_k = (q+1)w_{k-1} + q r_{k-1} $$

ここで、$w_{k-1} + r_{k-1}$ は $k-1$ 回目までの操作における再配分の総数であり、これは $s_k$ に等しい。すなわち $r_{k-1} = s_k - w_{k-1}$ である。これを上の式に代入すると、

$$ \begin{aligned} w_k &= (q+1)w_{k-1} + q(s_k - w_{k-1}) \\ &= w_{k-1} + q s_k \end{aligned} $$

問題の定義より $w_k = a_{k+1}$、$w_{k-1} = a_k$ であるから、

$$ a_{n+1} = a_n + q s_n $$

これと(2)の結果より、求める差は、

$$ a_{n+1} - a_n = q s_n = q(q+r)(q+r+1)^{n-2} $$

(4) (3)より、数列 $\{a_n\}$ の階差数列が $q(q+r)(q+r+1)^{n-2}$ であることがわかる。 $n \ge 3$ のとき、

$$ \begin{aligned} a_n &= a_2 + \sum_{k=2}^{n-1} (a_{k+1} - a_k) \\ &= q + \sum_{k=2}^{n-1} q(q+r)(q+r+1)^{k-2} \end{aligned} $$

シグマ部分は初項 $q(q+r)$、公比 $q+r+1$、項数 $n-2$ の等比数列の和であるから、

$$ \begin{aligned} a_n &= q + q(q+r) \frac{(q+r+1)^{n-2} - 1}{(q+r+1) - 1} \\ &= q + q \{ (q+r+1)^{n-2} - 1 \} \\ &= q(q+r+1)^{n-2} \end{aligned} $$

この結果は $n=2$ のとき $a_2 = q(q+r+1)^0 = q$ となり、(1)で求めた $a_2$ と一致するため $n=2$ でも成立する。したがって、

$$ a_n = q(q+r+1)^{n-2} $$

解説

玉に番号が振られているため、同じ色の玉であっても区別して場合の数を計算する必要がある点に注意が必要です。 (2)の $s_n$ は、$w_n$ と $r_n$ の連立漸化式の和をとって求めることも可能ですが、玉の総数だけに注目すれば「前の箱から何色の玉が来ようと、次の操作の選択肢は常に $q+r+1$ 通りである」という構造に気づき、より直接的に求めることができます。この $s_n$ を活用することで、(3)では連立漸化式を1つの階差数列の形に帰着でき、(4)でスムーズに一般項を求める誘導となっています。