トップ› 東京工業大学› 2001年› 理系第3問

東京工業大学 2001年理系第3問解説

方針・初手

「累積和 $X_j$ のいずれかが $k$ になる」という事象は、「カードの出目の合計がちょうど $k$ になる瞬間がある」ことと言い換えることができる。1回目に取り出すカードの番号で場合分けをして、確率の漸化式を作成する方針が汎用的で見通しが良い。また、(1)や(3)のような $k \leqq N$ の条件下では、出目に上限 $N$ の制限を受けないため、場合の数を直接数え上げて二項定理に帰着させる手法も有効である。

解法1

便宜上、和が $0$ になる確率を $P_N(0) = 1$ とし、$k < 0$ のときは $P_N(k) = 0$ と定めておく。 1回目に取り出すカードの番号を $i$ ($1 \leqq i \leqq N$) とする。その後、残りの試行で出目の和が $k-i$ に到達すればよいので、この事象が起こる条件付き確率は $P_N(k-i)$ である。各 $i$ が出る確率は $\frac{1}{N}$ であり、これらは排反であるから、

$$ P_N(k) = \frac{1}{N} \sum_{i=1}^{N} P_N(k-i) $$

が成り立つ。

(1) $N \geqq 3$ であるから、上の漸化式に $k=1, 2, 3$ を順次適用すると、

$$ \begin{aligned} P_N(1) &= \frac{1}{N} P_N(0) = \frac{1}{N} \\ P_N(2) &= \frac{1}{N} \{ P_N(1) + P_N(0) \} = \frac{1}{N} \left( \frac{1}{N} + 1 \right) = \frac{N+1}{N^2} \\ P_N(3) &= \frac{1}{N} \{ P_N(2) + P_N(1) + P_N(0) \} = \frac{1}{N} \left( \frac{N+1}{N^2} + \frac{1}{N} + 1 \right) = \frac{(N+1)^2}{N^3} \end{aligned} $$

(2) $N = 3$ のとき、(1) の結果より

$$ P_3(1) = \frac{1}{3}, \quad P_3(2) = \frac{4}{9}, \quad P_3(3) = \frac{16}{27} $$

となる。$k \geqq 4$ については、漸化式より $P_3(k) = \frac{1}{3} \{ P_3(k-1) + P_3(k-2) + P_3(k-3) \}$ であるから、

$$ \begin{aligned} P_3(4) &= \frac{1}{3} \{ P_3(3) + P_3(2) + P_3(1) \} \\ &= \frac{1}{3} \left( \frac{16}{27} + \frac{4}{9} + \frac{1}{3} \right) = \frac{16 + 12 + 9}{81} = \frac{37}{81} \\ P_3(5) &= \frac{1}{3} \{ P_3(4) + P_3(3) + P_3(2) \} \\ &= \frac{1}{3} \left( \frac{37}{81} + \frac{16}{27} + \frac{4}{9} \right) = \frac{37 + 48 + 36}{243} = \frac{121}{243} \end{aligned} $$

(3) $k \leqq N$ のとき、漸化式において $i > k$ の項は $P_N(k-i) = 0$ となるため、和は $i=k$ まででよい。

$$ P_N(k) = \frac{1}{N} \sum_{i=1}^{k} P_N(k-i) = \frac{1}{N} \{ P_N(k-1) + P_N(k-2) + \dots + P_N(0) \} $$

同様に、$k-1$ のとき（$k-1 < N$ であるから）

$$ P_N(k-1) = \frac{1}{N} \sum_{i=1}^{k-1} P_N(k-1-i) = \frac{1}{N} \{ P_N(k-2) + \dots + P_N(0) \} $$

これらを用いると、

$$ \begin{aligned} P_N(k) &= \frac{1}{N} P_N(k-1) + \frac{1}{N} \{ P_N(k-2) + \dots + P_N(0) \} \\ &= \frac{1}{N} P_N(k-1) + P_N(k-1) \\ &= \frac{N+1}{N} P_N(k-1) \end{aligned} $$

よって、数列 $\{ P_N(k) \}$ は初項 $P_N(1) = \frac{1}{N}$、公比 $\frac{N+1}{N}$ の等比数列となる。したがって、

$$ P_N(k) = \frac{1}{N} \left( \frac{N+1}{N} \right)^{k-1} = \frac{(N+1)^{k-1}}{N^k} $$

解法2

(1)と(3)について、直接確率の和として計算する別解を示す。

$k \leqq N$ のとき、和が $k$ になるまでに出るカードの番号はすべて $k$ 以下であり、カードの上限 $N$ による制限を考慮する必要がない。 $m$ 回目に初めて和が $k$ になるとする。このとき出たカードの番号を $y_1, y_2, \dots, y_m$ とすると、これらは $1 \leqq y_i \leqq N$ を満たす自然数であり、

$$ y_1 + y_2 + \dots + y_m = k $$

を満たす。$k \leqq N$ より $y_i \leqq N$ は自動的に満たされるため、制約は $y_i \geqq 1$ のみとなる。この方程式を満たす自然数の組 $(y_1, \dots, y_m)$ の個数は、$k$ 個の $1$ を横に並べ、その間の $k-1$ 個の隙間から $m-1$ 個を選んで仕切りを入れる方法の数に等しく、${}_{k-1}\mathrm{C}_{m-1}$ 通りである。

各組が出る確率は、1回の試行ごとに独立して $\frac{1}{N}$ であるため $\left(\frac{1}{N}\right)^m$ となる。和が $k$ になる試行回数 $m$ は $1$ から $k$ までの値をとりうる。これらは互いに排反であるため、

$$ \begin{aligned} P_N(k) &= \sum_{m=1}^{k} {}_{k-1}\mathrm{C}_{m-1} \left( \frac{1}{N} \right)^m \\ &= \frac{1}{N} \sum_{m=1}^{k} {}_{k-1}\mathrm{C}_{m-1} \left( \frac{1}{N} \right)^{m-1} \cdot 1^{k-m} \end{aligned} $$

二項定理 $(a+b)^{k-1} = \sum_{m=1}^{k} {}_{k-1}\mathrm{C}_{m-1} a^{m-1} b^{k-m}$ より、

$$ P_N(k) = \frac{1}{N} \left( \frac{1}{N} + 1 \right)^{k-1} = \frac{(N+1)^{k-1}}{N^k} $$

（3）の結果はこれである。また、（1）は $k=1, 2, 3$ の場合であり、$N \geqq 3$ より $k \leqq N$ を満たすためこの結果が適用できる。代入して計算すると、

$$ P_N(1) = \frac{1}{N}, \quad P_N(2) = \frac{N+1}{N^2}, \quad P_N(3) = \frac{(N+1)^2}{N^3} $$

となる。

解説

確率の漸化式を立てる際の基本となる良問である。「和が $k$ になる確率」を考える場合、最後に引いたカードで場合分けをする（後ろから考える）か、最初に引いたカードで場合分けをする（前から考える）かの2通りが考えられる。本問では「$i$ を引いてから残りの試行で和が $k-i$ を作る」と捉える方が、後続の試行回数が未定であっても $P_N(k-i)$ という形でシンプルに表現できる。解法2のように、カードの上限に引っかからない範囲（$k \leqq N$）であれば、和の分割（重複組合せ）を用いて直接計算することもでき、二項定理の見事な応用例となる。