トップ› 東京大学› 2001年› 文系第3問

東京大学 2001年文系第3問解説

方針・初手

2点A，Bの座標そのものではなく、その「差」に着目する。 $n$ 回目の試行後の点A，Bの座標をそれぞれ $a_n, b_n$ とし、その差を $d_n = a_n - b_n$ とおく。試行のルールに従って $d_n$ がどのように変化するか（状態遷移）を調べ、場合の数についての漸化式を立てる。

解法1

$n$ 回目の試行後の点A，Bの座標をそれぞれ $a_n, b_n$ とし、$d_n = a_n - b_n$ とおく。初期状態は $a_0 = 0, b_0 = 0$ であるから、$d_0 = 0$ である。

コインを投げたときの $d_n$ の変化を調べる。

（i）表が出た場合

$a_n > b_n$（すなわち $d_n > 0$）のとき、AとBを共に正の方向に1動かすため、$a_{n+1} = a_n + 1, b_{n+1} = b_n + 1$ となり、$d_{n+1} = d_n$ である。
そうでない（すなわち $d_n \leqq 0$）とき、Aのみ正の方向に1動かすため、$a_{n+1} = a_n + 1, b_{n+1} = b_n$ となり、$d_{n+1} = d_n + 1$ である。

（ii）裏が出た場合

$b_n > a_n$（すなわち $d_n < 0$）のとき、AとBを共に正の方向に1動かすため、$a_{n+1} = a_n + 1, b_{n+1} = b_n + 1$ となり、$d_{n+1} = d_n$ である。
そうでない（すなわち $d_n \geqq 0$）とき、Bのみ正の方向に1動かすため、$a_{n+1} = a_n, b_{n+1} = b_n + 1$ となり、$d_{n+1} = d_n - 1$ である。

これらをまとめると、$d_n$ の値は次のように推移する。

$d_n = 0$ のとき、表なら $d_{n+1} = 1$、裏なら $d_{n+1} = -1$
$d_n = 1$ のとき、表なら $d_{n+1} = 1$、裏なら $d_{n+1} = 0$
$d_n = -1$ のとき、表なら $d_{n+1} = 0$、裏なら $d_{n+1} = -1$

初期状態が $d_0 = 0$ であることから、任意の $n$ に対して $d_n$ は $-1, 0, 1$ のいずれかの値しかとらない。

(1)

$n$ 回の試行後、$d_n = 0, 1, -1$ となる場合の数をそれぞれ $X_n, Y_n, Z_n$ とおく。全事象の数は $2^n$ 通りであり、$d_n$ は $-1, 0, 1$ のいずれかであるから、

$$ X_n + Y_n + Z_n = 2^n $$

が成り立つ。

$n+1$ 回の試行後に $d_{n+1} = 0$ となるのは、

$n$ 回目の試行後に $d_n = 1$ であり、$n+1$ 回目に裏が出る場合
$n$ 回目の試行後に $d_n = -1$ であり、$n+1$ 回目に表が出る場合

のいずれかである。それぞれ1通りずつ存在するため、次の漸化式が成り立つ。

$$ X_{n+1} = Y_n + Z_n $$

上の2式から $Y_n + Z_n$ を消去すると、求める関係式は、

$$ X_{n+1} = 2^n - X_n $$

(2)

（1）で求めた漸化式 $X_{n+1} + X_n = 2^n$ の両辺を $2^{n+1}$ で割ると、

$$ \frac{X_{n+1}}{2^{n+1}} + \frac{1}{2} \frac{X_n}{2^n} = \frac{1}{2} $$

$x_n = \frac{X_n}{2^n}$ とおくと、

$$ x_{n+1} + \frac{1}{2} x_n = \frac{1}{2} $$

これを変形すると、

$$ x_{n+1} - \frac{1}{3} = -\frac{1}{2} \left( x_n - \frac{1}{3} \right) $$

ここで、1回目の試行後に $d_1 = 0$ となることはないため、$X_1 = 0$ である。したがって、$x_1 = \frac{X_1}{2^1} = 0$ となる。

数列 $\left\{ x_n - \frac{1}{3} \right\}$ は初項 $x_1 - \frac{1}{3} = -\frac{1}{3}$、公比 $-\frac{1}{2}$ の等比数列であるから、

$$ x_n - \frac{1}{3} = -\frac{1}{3} \left( -\frac{1}{2} \right)^{n-1} $$

$$ x_n = \frac{1}{3} - \frac{1}{3} \left( -\frac{1}{2} \right)^{n-1} $$

$X_n = 2^n x_n$ より、

$$ X_n = \frac{2^n}{3} - \frac{2^n}{3} \left( -\frac{1}{2} \right)^{n-1} $$

$$ X_n = \frac{2^n}{3} + \frac{2}{3} (-1)^n = \frac{2^n + 2(-1)^n}{3} $$

解法2

（2）の漸化式 $X_{n+1} = -X_n + 2^n$ を階差数列を用いて解く別解。

漸化式の両辺に $(-1)^{n+1}$ を掛けると、

$$ (-1)^{n+1} X_{n+1} = -(-1)^{n+1} X_n + (-1)^{n+1} 2^n $$

$$ (-1)^{n+1} X_{n+1} - (-1)^n X_n = -(-2)^n $$

数列 $\{(-1)^n X_n\}$ の階差数列が $-(-2)^n$ であることがわかる。 $n \geqq 2$ のとき、

$$ (-1)^n X_n = (-1)^1 X_1 + \sum_{k=1}^{n-1} \{-(-2)^k\} $$

$X_1 = 0$ であり、和の部分は初項 $2$、公比 $-2$、項数 $n-1$ の等比数列の和であるから、

$$ (-1)^n X_n = 0 - \frac{-2 \{1 - (-2)^{n-1}\}}{1 - (-2)} = \frac{2}{3} + \frac{1}{3} (-2)^n $$

$$ (-1)^n X_n = \frac{2}{3} + \frac{1}{3} (-1)^n 2^n $$

両辺に $(-1)^n$ を掛けると（$(-1)^{2n} = 1$ に注意して）、

$$ X_n = \frac{2}{3} (-1)^n + \frac{1}{3} 2^n = \frac{2^n + 2(-1)^n}{3} $$

この式は $n=1$ のときも $X_1 = \frac{2 - 2}{3} = 0$ となり成り立つ。

解説

2点の座標の「差」を状態として捉えることが最大のポイントである。状態遷移図を描くと、差が $-1, 0, 1$ の3つの状態間のみを行き来することが視覚的に理解できる。

（1）では、直接 $X_{n+1}$ を $X_n$ だけで表すことが難しく見えても、他の状態への遷移数を文字で置くことで、全体の和が $2^n$ であることを利用して鮮やかに漸化式を導くことができる。

（2）の漸化式 $X_{n+1} + X_n = 2^n$ は、$X_{n+1} - p \cdot 2^{n+1} = q(X_n - p \cdot 2^n)$ の形に変形して等比数列に帰着させる手法（解法1）が王道である。階差数列に持ち込む手法（解法2）も計算が簡潔になるため、身につけておくと時間の短縮や検算に役立つ。