トップ› 九州大学› 2004年› 理系第5問

九州大学 2004年理系第5問解説

方針・初手

各電球は赤色または青色になるため、 $n$ 個の電球の色の並び方は全部で $2^n$ 通りあり、これらは同様に確からしい。「色の変化」とは、隣り合う $2$ つの電球の色が異なる箇所の数である。電球と電球の「隙間」は $n-1$ 個あり、それぞれの隙間で色の変化が起きるか起きないかを考える。特定の条件を満たす色の並び方の総数を求め、全体の総数 $2^n$ で割ることで確率を計算するか、あるいは各隙間での変化の確率に着目する方針をとる。

解法1

$n$ 個の電球の色の並び方は全部で $2^n$ 通りあり、これらは同様に確からしい。隣り合う電球の間（隙間）は全部で $n-1$ 箇所ある。

(1)

左端が赤色で、色の変化がちょうど $1$ 回起きるのは、左端からある箇所までは赤色が続き、そこから右端までは青色が続く場合である。すなわち、色の変化が起きる箇所を $n-1$ 個の隙間から $1$ つ選べば、左端が赤色であることから全体の色の並びが一意に定まる。隙間の選び方は $n-1$ 通りあるので、条件を満たす並び方は $n-1$ 通り。よって、求める確率は

$$ \frac{n-1}{2^n} $$

(2)

「色の変化が少なくとも $2$ 回起きる」の余事象は、「色の変化が $0$ 回または $1$ 回起きる」である。

(i) 色の変化が $0$ 回起きる場合すべて赤色、またはすべて青色になる場合の $2$ 通りである。

(ii) 色の変化が $1$ 回起きる場合 (1)より、左端が赤色で変化が $1$ 回起きる場合は $n-1$ 通り。同様に、左端が青色で変化が $1$ 回起きる場合も $n-1$ 通りある。よって、色の変化が $1$ 回起きる並び方は $2(n-1)$ 通り。

(i), (ii) より、余事象の確率は

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

したがって、求める確率は

$$ 1 - \frac{n}{2^{n-1}} $$

(3)

色の変化がちょうど $m$ 回起きる並び方を考える。 $n-1$ 個の隙間から、色の変化が起きる箇所を $m$ 個選ぶ方法は ${}_{n-1}\mathrm{C}_m$ 通りある。変化が起きる箇所を固定したとき、左端の電球の色を赤または青の $2$ 通り決めると、以降のすべての電球の色が一意に定まる。したがって、色の変化がちょうど $m$ 回起きる並び方は $2 \times {}_{n-1}\mathrm{C}_m$ 通りである。よって、求める確率は

$$ \frac{2 \times {}_{n-1}\mathrm{C}_m}{2^n} = \frac{{}_{n-1}\mathrm{C}_m}{2^{n-1}} $$

(4)

(3)より、色の変化の回数が $m$ 回である確率を $p_m$ とすると、期待値 $E$ は

$$ E = \sum_{m=0}^{n-1} m \cdot p_m = \sum_{m=0}^{n-1} m \frac{{}_{n-1}\mathrm{C}_m}{2^{n-1}} $$

$m=0$ のときは項が $0$ になるため、$m=1$ からの和として計算する。ここで、$m \cdot {}_{n-1}\mathrm{C}_m$ について以下の変形を行う。

$$ m \cdot {}_{n-1}\mathrm{C}_m = m \cdot \frac{(n-1)!}{m!(n-1-m)!} = (n-1) \frac{(n-2)!}{(m-1)! \{(n-2)-(m-1)\}!} = (n-1) {}_{n-2}\mathrm{C}_{m-1} $$

これを用いると、

$$ E = \sum_{m=1}^{n-1} \frac{(n-1) {}_{n-2}\mathrm{C}_{m-1}}{2^{n-1}} = \frac{n-1}{2^{n-1}} \sum_{m=1}^{n-1} {}_{n-2}\mathrm{C}_{m-1} $$

$k = m-1$ とおくと、$m$ が $1$ から $n-1$ まで動くとき、$k$ は $0$ から $n-2$ まで動く。二項定理より、

$$ \sum_{k=0}^{n-2} {}_{n-2}\mathrm{C}_k = (1+1)^{n-2} = 2^{n-2} $$

したがって、

$$ E = \frac{n-1}{2^{n-1}} \cdot 2^{n-2} = \frac{n-1}{2} $$

解法2

事象の独立性と期待値の線形性を用いた解法。

左端の電球の色が何であれ、その右隣の電球の色が左の電球と異なる確率は $\frac{1}{2}$ であり、同じである確率も $\frac{1}{2}$ である。このことは、さらに右の電球についても同様に独立して成り立つ。すなわち、$n-1$ 箇所の各隙間において、色が変化する確率はそれぞれ独立に $\frac{1}{2}$ である。

(1)

左端が赤色になる確率は $\frac{1}{2}$ である。色の変化がちょうど $1$ 回起きるのは、$n-1$ 箇所の隙間のうち特定の $1$ 箇所でのみ色が変化し、残りの $n-2$ 箇所では色が変化しない場合である。どの箇所で変化するかは $n-1$ 通りあり、各隙間で変化する・しないの確率はそれぞれ $\frac{1}{2}$ である。よって求める確率は、

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

(2)

色の変化の回数は、試行回数 $n-1$、確率 $\frac{1}{2}$ の反復試行とみなせる。よって、余事象である「色の変化が $0$ 回または $1$ 回起きる」確率は、

$$ {}_{n-1}\mathrm{C}_0 \left(\frac{1}{2}\right)^0 \left(\frac{1}{2}\right)^{n-1} + {}_{n-1}\mathrm{C}_1 \left(\frac{1}{2}\right)^1 \left(\frac{1}{2}\right)^{n-2} = \frac{1}{2^{n-1}} + \frac{n-1}{2^{n-1}} = \frac{n}{2^{n-1}} $$

求める確率は、この余事象の確率を $1$ から引いて、

$$ 1 - \frac{n}{2^{n-1}} $$

(3)

同様に、 $n-1$ 箇所のうちちょうど $m$ 箇所で色の変化が起きる確率は、反復試行の確率より、

$$ {}_{n-1}\mathrm{C}_m \left(\frac{1}{2}\right)^m \left(\frac{1}{2}\right)^{n-1-m} = \frac{{}_{n-1}\mathrm{C}_m}{2^{n-1}} $$

(4)

左から $k$ 番目と $k+1$ 番目 ($1 \leqq k \leqq n-1$) の電球の色が異なる事象を $A_k$ とし、確率変数 $X_k$ を

$$ \begin{cases} X_k = 1 & (事象 A_k が起こるとき) \\ X_k = 0 & (事象 A_k が起こらないとき) \end{cases} $$

と定義する。 $A_k$ が起こる確率は $\frac{1}{2}$ なので、各 $X_k$ の期待値は

$$ E[X_k] = 1 \cdot \frac{1}{2} + 0 \cdot \frac{1}{2} = \frac{1}{2} $$

全体の色の変化の回数を $X$ とすると、$X = X_1 + X_2 + \cdots + X_{n-1}$ と表せる。期待値の線形性により、

$$ E[X] = E[X_1 + X_2 + \cdots + X_{n-1}] = \sum_{k=1}^{n-1} E[X_k] = \sum_{k=1}^{n-1} \frac{1}{2} = \frac{n-1}{2} $$

解説

本問は、一列に並んだ要素の状態変化を扱う確率の典型問題である。解法1のように全体の並び方 $2^n$ 通りを分母として、条件を満たす並び方を直接数え上げるのが最も素直なアプローチである。「電球の隙間」に着目すると、状態の変化を効率よく数えることができる。解法2のように、各隙間における「変化する／変化しない」がそれぞれ確率 $\frac{1}{2}$ の独立な事象であると捉えると、色の変化の回数は二項分布 $B(n-1, \frac{1}{2})$ に従うことがわかる。この見方ができれば、(3)までは反復試行の公式から直ちに立式でき、(4)も期待値の性質やインジケーター変数（確率変数の和）の知識を用いて計算量を大幅に減らすことが可能になる。