トップ› 東京大学› 2008年› 理系第2問

東京大学 2008年理系第2問解説

方針・初手

手持ちのカードについて、白と黒は対等な条件であるため、「少数派の色の枚数」に着目して状態を分類する。操作を行うごとに少数派の枚数がどのように変化するか、その遷移確率を求めて漸化式を立てる。求めるのは「初めて」すべて同じ色になる確率なので、すべて同じ色になった状態を吸収状態（それ以上遷移を考えない状態）として扱う。

解法1

(1)

$m$ 回目の操作を終えた時点での、手持ちのカードのうち「少数派の色の枚数」（両方2枚のときは2）を $X_m$ とおく。カードは全部で4枚なので、$X_m$ のとり得る値は $2, 1, 0$ のいずれかである。初期状態は白2枚黒2枚なので $X_0 = 2$ である。 4枚とも同じ色になるというのは、$X_m = 0$ となることと同値である。

各状態からの遷移確率は次のようになる。・$X_m = 2$ のとき 4枚中どのカードを選んで色を変えても、必ず一方が3枚、もう一方が1枚になる。よって、確率 $1$ で $X_{m+1} = 1$ となる。・$X_m = 1$ のとき手持ちは多数派が3枚、少数派が1枚である。確率 $\frac{1}{4}$ で少数派のカードが選ばれて色が変わると、4枚とも同じ色になり $X_{m+1} = 0$ となる。確率 $\frac{3}{4}$ で多数派のカードが選ばれて色が変わると、両方2枚ずつになり $X_{m+1} = 2$ となる。

$m$ 回目の操作後にまだ $X_m \neq 0$ であり、かつ $X_m = 2$ である確率を $a_m$、$X_m = 1$ である確率を $b_m$ とする。また、$m$ 回目に初めて $X_m = 0$ となる確率を $p_m$ とする。初期状態より $a_0 = 1, b_0 = 0, p_0 = 0$ である。上の遷移確率より、次の関係式が成り立つ。

$$ \begin{cases} a_m = \frac{3}{4} b_{m-1} \\ b_m = a_{m-1} \\ p_m = \frac{1}{4} b_{m-1} \end{cases} $$

$a_m$ と $b_m$ の式から $b_m$ を消去すると、$m \ge 2$ において以下の漸化式が得られる。

$$ a_m = \frac{3}{4} a_{m-2} $$

$a_0 = 1, a_1 = \frac{3}{4} b_0 = 0$ なので、$a_m$ は $m$ が奇数のときは $0$、偶数のときは $m = 2k$ （$k$ は $0$ 以上の整数）とおくと、

$$ a_{2k} = \left(\frac{3}{4}\right)^k $$

となる。求める確率 $p_n$ は、漸化式より $p_n = \frac{1}{4} b_{n-1} = \frac{1}{4} a_{n-2}$ （$n \ge 2$）と表せる。 $n$ が奇数のとき、$n-2$ も奇数なので $a_{n-2} = 0$ となり、$p_n = 0$ である。また、$n=1$ のときも $p_1 = \frac{1}{4} b_0 = 0$ となるため、奇数のときは常に $0$ である。 $n$ が偶数のとき、$n = 2k$ （$k \ge 1$）とおくと、

$$ p_{2k} = \frac{1}{4} a_{2k-2} = \frac{1}{4} \left(\frac{3}{4}\right)^{k-1} $$

これを $n$ を用いて書き直すと、$k = \frac{n}{2}$ より、

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

となる。

(2)

（1）と同様に、$m$ 回目の操作後の手持ちの6枚のカードのうち、「少数派の色の枚数」（両方3枚のときは3）を $Y_m$ とおく。 $Y_m$ のとり得る値は $3, 2, 1, 0$ のいずれかである。初期状態は白3枚黒3枚なので $Y_0 = 3$ である。 6枚とも同じ色になるというのは、$Y_m = 0$ となることと同値である。

各状態からの遷移確率は次のようになる。・$Y_m = 3$ のときどのカードを選んでも、一方が4枚、もう一方が2枚になる。よって、確率 $1$ で $Y_{m+1} = 2$ となる。・$Y_m = 2$ のとき多数派が4枚、少数派が2枚である。確率 $\frac{4}{6} = \frac{2}{3}$ で多数派が選ばれると、両方3枚になり $Y_{m+1} = 3$ となる。確率 $\frac{2}{6} = \frac{1}{3}$ で少数派が選ばれると、少数派が1枚になり $Y_{m+1} = 1$ となる。・$Y_m = 1$ のとき多数派が5枚、少数派が1枚である。確率 $\frac{5}{6}$ で多数派が選ばれると、少数派が2枚になり $Y_{m+1} = 2$ となる。確率 $\frac{1}{6}$ で少数派が選ばれると、6枚とも同じ色になり $Y_{m+1} = 0$ となる。

$m$ 回目の操作後にまだ $Y_m \neq 0$ であり、かつ $Y_m = 3, 2, 1$ である確率をそれぞれ $x_m, y_m, z_m$ とし、初めて $Y_m = 0$ となる確率を $q_m$ とする。初期状態より $x_0 = 1, y_0 = 0, z_0 = 0, q_0 = 0$ である。遷移確率より、次の関係式が成り立つ。

$$ \begin{cases} x_m = \frac{2}{3} y_{m-1} \\ y_m = x_{m-1} + \frac{5}{6} z_{m-1} \\ z_m = \frac{1}{3} y_{m-1} \\ q_m = \frac{1}{6} z_{m-1} \end{cases} $$

$y_m$ についての漸化式を作る。第2式に第1式と第3式を代入すると、$m \ge 2$ において、

$$ y_m = \frac{2}{3} y_{m-2} + \frac{5}{6} \left(\frac{1}{3} y_{m-2}\right) = \left(\frac{2}{3} + \frac{5}{18}\right) y_{m-2} = \frac{17}{18} y_{m-2} $$

初期値は $y_0 = 0$、$y_1 = x_0 + \frac{5}{6} z_0 = 1$ である。したがって、$y_m$ は $m$ が偶数のときは $0$、奇数のときは $m = 2k-1$ （$k \ge 1$）とおくと、

$$ y_{2k-1} = \left(\frac{17}{18}\right)^{k-1} y_1 = \left(\frac{17}{18}\right)^{k-1} $$

となる。求める確率 $q_n$ は、漸化式より $q_n = \frac{1}{6} z_{n-1} = \frac{1}{18} y_{n-2}$ （$n \ge 2$）と表せる。 $n$ が偶数のとき、$n-2$ も偶数なので $y_{n-2} = 0$ となり、$q_n = 0$ である。また、$q_1 = \frac{1}{6} z_0 = 0$ なので $n=1$ のときも $0$ である。 $n$ が3以上の奇数のとき、$n = 2k+1$ （$k \ge 1$）とおくと、$n-2 = 2k-1$ なので、

$$ q_{2k+1} = \frac{1}{18} y_{2k-1} = \frac{1}{18} \left(\frac{17}{18}\right)^{k-1} $$

これを $n$ を用いて書き直すと、$k = \frac{n-1}{2}$ より、

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

となる。

解説

白と黒の条件が対等であることに着目し、状態の持ち方を工夫することで状態の数を減らすのが定石である。今回は「少数派の枚数」という1つの変数だけで状態を表現できたため、確率の漸化式がシンプルになった。また、「初めて」という条件を満たすために、条件を達成した状態を吸収状態（そこから他へは遷移しない）として扱うことで、不要な重複カウントを防ぐことができる。 1手ごとに必ず「奇数と偶数」あるいは「両方奇数と両方偶数」といった偶奇の入れ替わりが発生するため、試行回数 $n$ の偶奇によって確率が $0$ になる点にも注意したい。