コイントス確率と重複組み合わせの難問 – 2022年東大 数学 第6問
2022年東大 数学 第6問 小問2の解法
小問1での考察により、 X200 が原点 O にいるための必要条件は r が3の倍数であることです。そこで r = 3l と置きます ( 0 ≦ l ≦ 63 ) 。
X200 が原点 O にいるための必要十分条件は
N_a = N_b = N_c
であったので、
N_a = N_b = N_c=l
が成り立ちます。
これが成り立つように表が出る必要があって、どういう場合にそうなるかは簡単に求められそうにない気がします。 m 投目が表だったとして、これ以前の裏の回数が３で割って１余るのか、２余るのか、割り切れるのかは、いろいろなバリエーションがあって洗い出すのは大変です。
しかし、何投目が表か裏か、という視点から離れて、例えば裏が６回出た直後の表、というように投げた回数から離れてみると、その表の前に表がいくつ出ていてもこれが「裏が６回出た直後の表」であることは変わりがありません。
そこで小問1での定義に従って、 200 以下の自然数のうちコイントスして表が出た回の集合を H200 と表記し、また非負整数 km を、コインを m 回投げたときに裏が出た回数と定義して
\begin{aligned}
A_{200} =\{m \in H_{200} | k_m \equiv 0 \mod 3 \} \\
B_{200} =\{m \in H_{200} | k_m \equiv 1 \mod 3 \} \\
C_{200} =\{m \in H_{200} | k_m \equiv 2 \mod 3 \} \\
\end{aligned}と定義するとき、
\begin{aligned}
A_{200} =\{m \in H_{200} | k_m =0,3,6, \cdots ,198-r \text{ } \\
\text{のいずれか} \} \\
B_{200} =\{m \in H_{200} | k_m =1,4,7, \cdots ,199-r \text{ }\\
\text{のいずれか} \} \\
C_{200} =\{m \in H_{200} | k_m =2,5,8, \cdots ,200-r\text{ } \\
\text{のいずれか} \} \\
\end{aligned}ですが、たとえば Na = #A200 = l が成り立つ場合の数は B200 や C200 の要素の存在バリエーションに影響されません。例えば裏1回目の直後に表が何回出ていても、どうでもいいということです。
そしてその場合の数は集合 { 0,3,6, …,198-r } から重複を許してl 個を取り出す場合の数と等しくなります。すなわち、
裏0回直後の表回数 a0
裏3回直後の表回数 a3
裏6回直後の表回数 a6
︙
裏198-r回直後の表回数 a198-r
と置くとき、各 ai が非負整数でかつ、 a0+a3+…a198-r=l を満たすように動くときの場合の数です。
集合 { 0,3,6, …,198-r } の要素数は 67-l なので、Na = l が成り立つ場合の数は 67-l 個の要素から重複を許して l 個を取り出す場合の数です。
同様の考察により、 Nb=l が成り立つ場合の数、および Nc=l が成り立つ場合の数も 67-l 個の要素から重複を許して l 個を取り出す場合の数であることがわかります。
従って求める確率は
\frac{ \left (\begin{aligned} & 67-l \text{個の要素から重複を許して } \\ &l \text{個を取り出す場合の数} \end{aligned} \right) ^3}{2^{200}}です。
67-l 個の要素から重複を許して l 個を取り出す場合の数を求める
求める場合の数は、 67-l 個の箱に l 個の玉を入れるときのバリエーションです。玉の数が 0 の箱があってもいいというところがポイントです。どの箱も最低1個入れるという条件であれば、以下のように1列に並べた玉と玉の間に(箱の数-1)枚の仕切りを入れる場合の数として求められます。その値は(玉の数-1)個のものから(箱の数-1)個のものを選ぶ組み合わせの数です。以下に6個の玉を4つの箱に入れる場合のイメージを示します。
○○|○○|○|○
○○|○|○|○○
○|○|○○○|○
︙
ところが空の箱があっていいという条件なので、(箱の数-1)枚の仕切りの入れ方は玉の前後に何枚か（複数可）入れる、ということになります。以下に6個の玉を4つの箱に入れる場合（箱が空の場合あり）のイメージを示します。
○○|○○|○|○
○○||○○|○○
|○|○○○○○|
︙
仕切りが連続しているのは、対応する箱が空であることを表しています。
ここで|を●に置き換えて表現してみます。
○○●○○●○●○
○○●●○○●○○
●○●○○○○○●
︙
このように表現することで、求める場合の数が(玉の数+箱の数-1)個のものから(玉の数)個のものを取り出す組み合わせの数であることがわかります。上記の6個の玉を4つの箱に入れる場合（箱が空の場合あり）の数は、 9C6 = 84 とおりです。
以上の考察により、67-l 個の要素から重複を許して l 個を取り出す場合の数は、 67-l 個の箱に l 個の玉を入れる場合（箱が空の場合あり）の数で、それは
{}_{67-l + l -1} \mathrm{C}_{l} = {}_{66}\mathrm{C}_{l}です。 r=3l であったので、求める確率 prは
p_r = \left \{ \begin{aligned}
& \frac{ ( {}_{66} \mathrm{C}_{ \frac{r}3} )^3}{2^{200}} & (r \equiv0 \mod 3) \\
& 0 &(r \not\equiv 0 \mod 3)
\end{aligned}
\right .です。
pr が最大になる r は 66Clが最大になる l の3倍で、そのような l は \displaystyle\frac{66}2 = 33 に最も近い値すなわち 33 です。
これは自明な気がしますが、念の為証明を用意しておきます。自然数 n と r \leqq [ \displaystyle\frac{n}{2}] である自然数 r に対し、
\begin{aligned}
& {}_n \mathrm{C}_r - {}_n \mathrm{C}_{r-1} \\
= & \frac{n!}{r!(n-r)!} - \frac{n!}{(r-1)!(n-r +1)!} \\
= & \frac{n!}{(r-1)!(n-r )!} \left( \frac{1}{r} -\frac{1}{n-r+1} \right) \\
= & \frac{n!}{r!(n-r+1 )!} (n-r+1-r) \\
= & \frac{n!}{r!(n-r+1 )!} (n-2r+1) \\
\geqq & \frac{n!}{r!(n-r+1 )!} (n-2 \left[\frac{n}{2} \right]+1) \\
\geqq & \frac{n!}{r!(n-r+1 )!} > 0
\end{aligned}です。
ゆえにpr が最大になる r は 33 ☓ 3 = 99 です。