コイントス確率と重複組み合わせの難問 – 2022年東大 数学 第6問
発展 – 重複組み合わせ
本稿に出てきた、 n 個の箱に l 個の玉を箱が空である場合を許して入れる場合の数を重複組み合わせといい、その値は
{}_{n+l-1} \mathrm{C}_lで求められます。
このことは教科書に発展的内容として掲載されているので、もし知っていれば無証明で使用してOKです。
しかし重複組み合わせを知らないと本問の小問2はかなり厳しくなりますが、解けないわけではありません。 n 個の箱のうち j 個 (1 ≦ j ≦ n ) の箱に 、l 個の玉をどの箱にも最低1個入れる場合の数は
\begin{aligned}
& {}_n \mathrm{C}_j \cdot {}_{l-1} \mathrm{C}_{j -1} & ( j \leqq l) \\
& 0 &( j > l) \\
\end{aligned}であるので、 n 個の箱に l 個の玉を箱が空である場合を許して入れる場合の数は
\sum_{j=1}^l{}_n \mathrm{C}_j \cdot {}_{l-1} \mathrm{C}_{j -1}です。したがって
p_r = \left \{ \begin{aligned}
& \frac{( \sum_{j=1}^{\frac{r}{3}}{}_{67 -\frac{r}{3}} \mathrm{C}_j \cdot {}_{\frac{r}{3}-1} \mathrm{C}_{j -1} )^3}{2^{200}} \\ & \text{ } (r \equiv0 \mod 3) \\
& 0 \text{ } (r \not\equiv 0 \mod 3)
\end{aligned}
\right .が成り立つはずです。
実はこれは正しいので、このように回答してもそこそこ点数はもらえると思います。
しかしこれだと、 pr が最大になる r を求めることは非常に困難なので、
\sum_{j=1}^l{}_n \mathrm{C}_j \cdot {}_{l-1} \mathrm{C}_{j -1} = {}_{n+l-1} \mathrm{C}_lであることを何としても証明したいところです。
それにはまず、そういう式が成り立つことに気づく必要があります。
こういう場合の常套手段として、 l の値を色々動かして傾向を見ましょう。
まず l=1 のとき、
\sum_{j=1}^1{}_n \mathrm{C}_j \cdot {}_{0} \mathrm{C}_{j -1} ={}_n \mathrm{C}_1= nです。
次に l=2 のとき、
\begin{aligned}
& \sum_{j=1}^2{}_n \mathrm{C}_j \cdot {}_{1} \mathrm{C}_{j -1} \\
= & {}_n \mathrm{C}_1 + {}_n \mathrm{C}_2 \\
= & n + \frac{n(n-1)}2 \\
= & \frac{n(n+1)}2 \\
\end{aligned}です。
更に l=3 のとき、
\begin{aligned}
& \sum_{j=1}^3{}_n \mathrm{C}_j \cdot {}_{2} \mathrm{C}_{j -1} \\
= & {}_n \mathrm{C}_1 + 2 {}_n \mathrm{C}_2 + {}_n \mathrm{C}_3 \\
= & n +n(n-1)+ \frac{n(n-1)(n-2)}6 \\
= & n +\frac{n(n-1)(6+n-2)}6 \\
= & \frac{n(6+n^2+3n -4)}6 \\
= & \frac{n(n+1)(n+2)}6 \\
\end{aligned}です。
ここまで計算してみると、何となく
\begin{aligned}
& \sum_{j=1}^l{}_n \mathrm{C}_j \cdot {}_{l-1} \mathrm{C}_{j -1} \\
= & \frac{n(n+1)(n+2) \cdots (n+l-1)}{l!} \\
= & \frac{(n+l-1)!}{l!(n-1)!} \\
= & {}_{n+l-1} \mathrm{C}_l
\end{aligned}が成り立っていそうだと当たりが付けられます。
ここで改めて
{}_n \mathrm{C}_j \cdot {}_{l-1} \mathrm{C}_{j -1} に着目します。この式の意味するところは、「n 個の黒玉●から j 個を取り出す場合の数 ☓ l-1 個の白玉○から j-1 個を取り出す場合の数」です。●と○の合計が n+l-1 なので取り出す玉の数の合計が l 個になったりすると嬉しいところですが、残念ながらその数は 2j-1 個です。
何とかならないのかといろいろ考えているうちに
{}_{l-1} \mathrm{C}_{j -1} = {}_{l-1} \mathrm{C}_{l-j} であることに気がつければ勝ちです。
{}_n \mathrm{C}_j \cdot {}_{l-1} \mathrm{C}_{l-j} は「n 個の●から j 個を取り出す場合の数 ☓ l-1 個の○から l–j 個を取り出す場合の数」であり、取り出す玉の数は●○合わせて l 個です。
したがって、
\begin{aligned}
& \sum_{j=1}^l{}_n \mathrm{C}_j \cdot {}_{l-1} \mathrm{C}_{j -1} \\
= & \sum_{j=1}^l \left \{ \begin{aligned} & \left( \begin{aligned} n\text{個の●から}j \text{個を} \\ \text{取り出す場合の数} \end{aligned} \right) \\ &\times \left ( \begin{aligned} l-1\text{個の○から}l-j \text{個を} \\\text{取り出す場合の数} \end{aligned} \right) \end{aligned} \right \}\\
= & \left( \begin{aligned} & n\text{個の●と} l-1 \text{個の○から} \\ & \text{合わせて} l\text{個を取り出す場合の数} \end{aligned} \right ) \\
= & \left( \begin{aligned} & n+l-1\text{個の玉から} \\ & l \text{個を取り出す場合の数} \end{aligned} \right) \\
= & {}_{n+l-1} \mathrm{C}_l
\end{aligned}であり、やや定性的ながらこの内容で行けると思います。なお、数学的帰納法でより「数学っぽく」証明することも可能です。
しかしながら、ここまでたどり着くのに結構な時間がかかるので、重複組み合わせを知らない場合は適当なところで切り上げて他の問題に時間を使ったほうが良いでしょう。
解法のポイント
コイントスにベクトルが絡んで危険な香りプンプンですが、実はベクトルは単なる虚仮威しで、裏が出た回数の3を法とする剰余類がポイントであることに気がつくことが第1歩です。
これに気がつければ小問1は何とか解けるでしょう。
小問2は放ってしまうのが一般には正しい選択ですが、何投目が表か裏かという発想から離れて、裏の出方のバリエーションがキモであること、それが「67-l 個の要素から重複を許して l 個を取り出す場合の数」であることに気付くことができれば、本稿で示したように先が見えてきます。
更には、重複組み合わせを知っていることが死活的に重要です。この機会に覚えておきましょう。また、本稿で導出した
\sum_{j=1}^l{}_n \mathrm{C}_j \cdot {}_{l-1} \mathrm{C}_{j -1} = {}_{n+l-1} \mathrm{C}_lはどこかで使えるかもしれないので、合わせて覚えておきましょう。