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

方針・初手

玉にはすべて異なる番号がついているため区別される。したがって、最終的な玉の再配分が異なることは、各箱からどの玉を選んで次の箱に移動させるかの「選び方」が異なることと1対1に対応する。再配分の総数を求めるには、各移動段階での玉の選び方の総数を掛ければよい。

1番から $n$ 番の箱に向けて順に1個ずつ玉を移動させるため、各段階で対象となる箱に入っている玉の総数を正確に把握する。また、$n$ 番の箱の白玉が $q+1$ 個になるのは、最後に $n-1$ 番の箱から $n$ 番の箱へ白玉が移動してきた場合であることに着目し、各段階で白玉・赤玉が移動する場合の数を状態遷移として捉える。

解法1

すべての玉は番号で区別されるため、最終的な再配分の総数は、各操作においてどの玉を選ぶかの選び方の総数に等しい。

$k$ 番の箱から $k+1$ 番の箱へ1個の玉を移す操作を「第 $k$ 回の移動」と呼ぶ。移動は第 $1$ 回から第 $n-1$ 回まで順に行われる。

各移動を行う直前の箱の中身の総数を考える。

• 第 $1$ 回の移動：1番の箱には初期状態の白玉 $q$ 個、赤玉 $r$ 個の合計 $q+r$ 個がある。したがって、玉の選び方は $q+r$ 通りである。
• 第 $k$ 回の移動（$k \ge 2$）：$k$ 番の箱には初期状態の $q+r$ 個に加えて、第 $k-1$ 回の移動で直前の箱から入ってきた1個の玉があるため、合計 $q+r+1$ 個の玉がある。したがって、玉の選び方は $q+r+1$ 通りである。

これらの選択はすべて独立に行われるため、再配分の総数 $s_n$ ($n \ge 2$) は以下のようになる。

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

(1) $s_2$ を求める。

$n=2$ のとき、第1回の移動のみを行うので、選び方の総数は以下のようになる。

$$ s_2 = q+r $$

(2) $s_3$ と $a_3$ を求める。

$n=3$ のとき、再配分の総数 $s_3$ は、上記の式より以下のようになる。

$$ s_3 = (q+r)(q+r+1) $$

次に $a_3$ を求める。3番の箱からは玉を取り出さないため、3番の箱の白玉が $q+1$ 個になるのは、第2回の移動で2番の箱から3番の箱へ白玉が移動したときである。

第 $k$ 回の移動で白玉が選ばれる場合の数を $W_k$、赤玉が選ばれる場合の数を $R_k$ とする。第1回の移動では、1番の箱にある白玉 $q$ 個、赤玉 $r$ 個から選ぶため、以下の通りとなる。

$$ W_1 = q, \quad R_1 = r $$

第1回の移動を終えた直後の2番の箱の状態は、第1回で移された玉の色によって以下の2つの場合に分かれる。

• 第1回で白玉が移された場合（$W_1$ 通り）：2番の箱には白玉 $q+1$ 個、赤玉 $r$ 個がある。ここから白玉を選ぶ方法は $q+1$ 通りである。
• 第1回で赤玉が移された場合（$R_1$ 通り）：2番の箱には白玉 $q$ 個、赤玉 $r+1$ 個がある。ここから白玉を選ぶ方法は $q$ 通りである。

したがって、第2回の移動で白玉が選ばれる場合の数 $a_3 = W_2$ は、

$$ \begin{aligned} a_3 = W_2 &= W_1(q+1) + R_1 q \\ &= q(q+1) + r q \\ &= q(q+r+1) \end{aligned} $$

(3) $s_4$ と $a_4$ を求める。

$n=4$ のとき、再配分の総数 $s_4$ は、

$$ s_4 = (q+r)(q+r+1)^2 $$

次に $a_4$ を求める。(2) と同様に考えると、第 $k+1$ 回の移動で白玉が選ばれる場合の数 $W_{k+1}$ は、第 $k$ 回の移動で白玉が選ばれた場合と赤玉が選ばれた場合を合わせて、以下の漸化式で表される。

$$ W_{k+1} = W_k(q+1) + R_k q $$

これを変形すると、以下のようになる。

$$ W_{k+1} = W_k + q(W_k + R_k) $$

ここで、$W_k + R_k$ は第 $k$ 回の移動におけるすべての玉の選び方の総数であり、これは $k+1$ 番の箱までの再配分の総数 $s_{k+1}$ に等しい。すなわち、

$$ W_k + R_k = s_{k+1} $$

よって、漸化式は次のように書ける。

$$ W_{k+1} = W_k + q s_{k+1} $$

$a_4$ は第3回の移動で白玉が選ばれる場合の数 $W_3$ であるため、これまでに求めた $W_2$ ($=a_3$) と $s_3$ を用いて計算できる。

$$ \begin{aligned} a_4 = W_3 &= W_2 + q s_3 \\ &= q(q+r+1) + q(q+r)(q+r+1) \\ &= q(q+r+1) \{1 + (q+r)\} \\ &= q(q+r+1)^2 \end{aligned} $$

解説

場合の数の問題において、段階的な操作が繰り返される場合は、樹形図のように前の状態からの遷移を考えることが基本となります。本問では、前の箱から「白玉が来たか」「赤玉が来たか」で、次の箱から玉を取り出す際の選択肢の数が変わるため、それぞれの場合の数を $W_k, R_k$ と設定して漸化式を立てるアプローチが非常に有効です。

また、$W_k + R_k = s_{k+1}$ という全体の場合の数との関係式に気づくことで、直接的な場合分けによる煩雑な計算を避け、見通しよく解き進めることができます。

答え

(1) $s_2 = q+r$

(2) $s_3 = (q+r)(q+r+1), \quad a_3 = q(q+r+1)$

(3) $s_4 = (q+r)(q+r+1)^2, \quad a_4 = q(q+r+1)^2$