北海道大学 2011年度 前期日程 第2次学力試験理系数学 第4問

各箱にもともと入っている玉の総数を $m=q+r$ とおく。玉には番号がついているので、同じ色でも別々の玉として区別する。

各操作で右隣へ移される玉を順に見れば、最終的な再配分はその列で決まる。1回目は箱1にもともとある $m$ 個から選ぶので $m$ 通りである。2回目以降は、直前に左から入ってきた玉をそのまま右へ送る1通り、またはその箱にもともとある $m$ 個から新しく選ぶ $m$ 通りで、合わせて $m+1$ 通りである。

(1)
$n=2$ のとき、2番の箱へ入る玉が白玉であるためには、箱1の白玉を選べばよい。箱1には白玉が $q$ 個あるので $a_2=q$ である。

$n=3$ のとき、3番の箱へ最後に入る玉が白玉である場合を数える。1回目に箱1の白玉を選び、それを2回目にそのまま送る場合が $q$ 通りある。また、1回目には任意の $m$ 個のどれを選んでもよく、2回目に箱2にもともとある白玉を新しく選ぶ場合が $mq$ 通りある。したがって $$a_3=q+mq=q(m+1)=q(q+r+1)$$ である。

(2)
$n$ 個の箱では、操作は $n-1$ 回行われる。1回目が $m$ 通り、残りの $n-2$ 回がそれぞれ $m+1$ 通りなので $s_n=m(m+1{)}^{n-2}$ である。すなわち $s_n=(q+r)(q+r+1{)}^{n-2}$ である。

(3)
まず $a_n$ の構造を考える。最後にn番の箱へ入る玉が白玉なら、n番の箱の白玉はもともとの $q$ 個に1個増えて $q+1$ 個になる。逆に、n番の箱の白玉が $q+1$ 個になるには、最後に入る玉が白玉でなければならない。

最後に入る玉を白玉にするには、最初または途中のどこかで白玉を新しく選び、その後はそれを送ってもよいし、途中で別の選択をして最終的に白玉を選んでもよい。各段階での選択構造は、最後の色だけを指定した場合、最初に白玉を選ぶ $q$ 通りと、その後の $n-2$ 回の選択 $m+1$ 通りで整理できる。したがって $a_n=q(m+1{)}^{n-2}$ である。

よって $$a_{n+1}-a_n=q(m+1{)}^{n-1}-q(m+1{)}^{n-2}$$ であり、$$a_{n+1}-a_n=qm(m+1{)}^{n-2}$$ となる。すなわち $$a_{n+1}-a_n=q(q+r)(q+r+1{)}^{n-2}$$ である。

(4)
(3)で述べた通り、最後に送られる玉が白玉である場合を直接数えると $a_n=q(m+1{)}^{n-2}$ である。したがって $a_n=q(q+r+1{)}^{n-2}$ である。