コイントス確率と重複組み合わせの難問 – 2022年東大 数学 第6問
2022年東大 数学 第6問 はコイントスを複数回試行して条件に合う確率を求める問題ですが、えらく難しいのではっきり言って捨て問です。問題文は以下のとおりで、東大第２次試験問題からの引用です。
O を原点とする座標平面上で考える。0 以上の整数 k に対して，ベクトル \overrightarrow{v_k} を
\overrightarrow{v_k}= \left ( \cos \frac{2k \pi}3, \sin \frac{2k \pi}3 \right )と定める。投げたとき表と裏がどちらも \displaystyle\frac{ 1}2 の確率で出るコインを N 回投げて，座標平面上に点 X0,X1,X2,…,XN を以下の規則(i), (ii)に従って定める。
(i) X0 は O にある。
(ii) n を 1 以上 N 以下の整数とする。Xn−1 が定まったとし，Xn を次のように定める。
・n 回目のコイン投げで表が出た場合，
\overrightarrow{\mathrm{OX}_n} = \overrightarrow{\mathrm{OX}_{n-1}} + \overrightarrow{v_k}により，Xn を定める。ただし，k は 1 回目から n 回目までのコイン投げで裏が出た回数とする。
・n 回目のコイン投げで裏が出た場合，Xnを Xn−1 と定める。
(1) N=8 とする。X8 が O にある確率を求めよ。
(2) N=200 とする。X200 が O にあり，かつ，合計 200 回のコイン投げで表がちょうど r 回出る確率を pr とおく。ただし，0 ≦ r ≦ 200 である。pr を求めよ。また pr が最大となる r の値を求めよ。
コイントスにベクトルが組み合わさって、早くも嫌な予感がします。それでは見ていきましょう。なお、以下の内容は東京大学が発表したものではありません。
2022年東大 数学 第6問 小問1の解法
X8 がどういう条件のときに O に戻るか、傾向を探る
まず、8回コイントスして何回表なら X8 が原点 O に戻るかを考えます。
明らかに全回裏なら、 Xn はすべて O 上にいるので X8 も O 上にいます。
では逆に、全回表ならどうでしょうか。
考えを整理するため、記号を用意します。
明らかに
\overrightarrow{v_{k}} =
\left \{
\begin{aligned}
& (1 ,0) & ( k \equiv 0 \mod 3)\\
& \left ( - \frac{1}{2} , \frac{\sqrt{3}}{2} \right ) & ( k \equiv 1 \mod 3 )\\
& \left (- \frac{1}{2} , -\frac{\sqrt{3}}{2} \right) & ( k \equiv 2 \mod 3 )
\end{aligned}
\right.なので、
\begin{aligned}
\overrightarrow{a} = & (1 ,0) \\
\overrightarrow{b} = & \left ( - \frac{1}{2} , \frac{\sqrt{3}}{2} \right ) \\
\overrightarrow{c} =& \left (- \frac{1}{2} , -\frac{\sqrt{3}}{2} \right)
\end{aligned}
と置きます。明らかにこれら３つのベクトルの任意の２つは線形独立です。また、
\overrightarrow{a} + \overrightarrow{b} + \overrightarrow{c} = 0が成り立ちます。
このとき
\begin{aligned}
\overrightarrow{ \mathrm{OX}_1 } = & \overrightarrow{ v_0 } = \overrightarrow{ a } \\
\overrightarrow{ \mathrm{OX}_2 } = & \overrightarrow{ \mathrm{OX}_1 } +\overrightarrow{ v_0 } = 2 \overrightarrow{ a } \\
\overrightarrow{ \mathrm{OX}_3 } = & \overrightarrow{ \mathrm{OX}_2 } +\overrightarrow{ v_0 } = 3 \overrightarrow{ a } \\
\vdots \\
\overrightarrow{ \mathrm{OX}_8 } = & \overrightarrow{ \mathrm{OX}_7 } +\overrightarrow{ v_0 } = 8 \overrightarrow{ a }
\end{aligned}なので、X8 は O に戻りません。
では、表が1回だけ出たときはどうでしょうか。
m1 ( 1 ≦ m1 ≦ 8 ) 回目のコイントスでだけ表が出たとします。すると
\begin{aligned}
\overrightarrow { \mathrm{OX}_8 } & = \overrightarrow { \mathrm{OX}_{m_1} } \\
& =\overrightarrow { \mathrm{OX}_{m_1 -1} } + \overrightarrow {v_{m_1-1}} \\
& =\overrightarrow { \mathrm{OX}_{0} } + \overrightarrow {v_{m_1-1}} \\
& =\overrightarrow { \mathrm{OO} } + \overrightarrow {v_{m_1-1}} \\
& = \overrightarrow {v_{m_1-1}}
\end{aligned}ですが、 \overrightarrow {v_{m_1-1}} は \overrightarrow{a}, \overrightarrow{b} , \overrightarrow{c} のいずれかであり、それらはすべて０ベクトルではないので X8 は O に戻りません。
次に表が2回だけ出た場合を考えます。
m1 , m2 ( 1 ≦ m1 ＜ m2 ≦ 8 ) 回目のコイントスでだけ表が出たとします。すると
\begin{aligned}
\overrightarrow { \mathrm{OX}_8 } &= \overrightarrow { \mathrm{OX}_{m_2} } \\
& = \overrightarrow { \mathrm{OX}_{m_2-1} } + \overrightarrow {v_{m_2-2}}\\
& = \overrightarrow { \mathrm{OX}_{m_1} } + \overrightarrow {v_{m_2-2}}\\
& = \overrightarrow { \mathrm{OX}_{m_1-1} } + \overrightarrow {v_{m_1-1}} + \overrightarrow {v_{m_2-2}}\\
& = \overrightarrow { \mathrm{OX}_{0} } +\overrightarrow {v_{m_1-1}} + \overrightarrow {v_{m_2-2}} \\
& = \overrightarrow {v_{m_1-1}} + \overrightarrow {v_{m_2-2}}
\end{aligned}ですが、 \overrightarrow {v_{m_1-1}}, \overrightarrow {v_{m_2-2}} は \overrightarrow{a}, \overrightarrow{b} , \overrightarrow{c} のいずれかです（同じベクトルである場合もある）。
\overrightarrow {v_{m_1-1}} \ne \overrightarrow {v_{m_2-2}} の場合、 \overrightarrow{a}, \overrightarrow{b} , \overrightarrow{c} のうちの任意の２ベクトルは線形独立なので X8 は O に戻りません。 \overrightarrow {v_{m_1-1}}= \overrightarrow {v_{m_2-2}} の場合も明らかに、 X8 は O に戻りません。
ここまで考えたところで、
\overrightarrow{a} + \overrightarrow{b} + \overrightarrow{c} = 0であることから、表が3回出れば行けるのではないかという気がしてきます。
実際、1回目、3回目、5回目にのみ表が出たとすると、
\begin{aligned}
\overrightarrow { \mathrm{OX}_8 } &= \overrightarrow { \mathrm{OX}_{5} } \\
& = \overrightarrow { \mathrm{OX}_{4} } + \overrightarrow {v_{2}}\\
& = \overrightarrow { \mathrm{OX}_{3} } + \overrightarrow {v_{2}}\\
& = \overrightarrow { \mathrm{OX}_{2} } + \overrightarrow {v_{1}} + \overrightarrow {v_{2}}\\
& = \overrightarrow { \mathrm{OX}_{1} } + \overrightarrow {v_{1}} + \overrightarrow {v_{2}}\\
& = \overrightarrow { \mathrm{OX}_{0} } + \overrightarrow {v_{0}}+ \overrightarrow {v_{1}} + \overrightarrow {v_{2}}\\
& = \overrightarrow {v_{0}}+ \overrightarrow {v_{1}} + \overrightarrow {v_{2}}\\
& = \overrightarrow{a} + \overrightarrow{b} + \overrightarrow{c} = \overrightarrow{0}
\end{aligned}であり、X8 は O に戻ります。
しかし、1回目、4回目、5回目にのみ表が出た場合は
\begin{aligned}
\overrightarrow { \mathrm{OX}_8 } &= \overrightarrow { \mathrm{OX}_{5} } \\
& = \overrightarrow { \mathrm{OX}_{4} } + \overrightarrow {v_{2}}\\
& = \overrightarrow { \mathrm{OX}_{3} } + 2\overrightarrow {v_{2}}\\
& = \overrightarrow { \mathrm{OX}_{1} } + 2 \overrightarrow {v_{2}}\\
& = \overrightarrow { \mathrm{OX}_{0} } + \overrightarrow {v_{0}}+ 2 \overrightarrow {v_{2}}\\
& = \overrightarrow {v_{0}}+ 2 \overrightarrow {v_{2}}\\
& = \overrightarrow{a} +2 \overrightarrow{c} \ne \overrightarrow{ 0}
\end{aligned}であり、X8 は O に戻りません。どうも、表が出る回数が３なだけではだめで、
\overrightarrow{\mathrm{OX}_8} = \overrightarrow{a} + \overrightarrow{b} + \overrightarrow{c} が成り立つ必要がありそうです。
Xn が原点 O に存在するための必要十分条件
ところで \overrightarrow{ \mathrm{OX}_n } は \overrightarrow{v_k} の有限個の和ですが、 \overrightarrow{v_k} は \overrightarrow{a} , \overrightarrow{b} , \overrightarrow{c} のいずれかなので、ある非負整数 N_{a},N_{b},N_{c} が存在して
\overrightarrow{ \mathrm{OX}_n } = N_{a}\overrightarrow{a} + N_{b}\overrightarrow{b} + N_{c} \overrightarrow{c} が成り立ちますが、ここまで考察から、Xn が原点 O に存在するための必要十分条件は
N_{a} = N_{b} = N_{c}であると言えそうです。
これが十分条件であることは明らかです。また、 N_a,N_b,N_c が全て同じ値でないとき、仮に N_a が最小であったとすると、
\begin{aligned}
\overrightarrow{ \mathrm{OX}_n } = & N_a( \overrightarrow{a} + \overrightarrow{b} + \overrightarrow{c} )\\
& + ( N_b - N_a) \overrightarrow{b} + (N_c- N_a) \overrightarrow{c} \\
= & N_a\overrightarrow{0} + ( N_b - N_a) \overrightarrow{b} + (N_c- N_a) \overrightarrow{c} \\
= & ( N_b - N_a) \overrightarrow{b} + (N_c- N_a) \overrightarrow{c} \\
\end{aligned}ですが、 \overrightarrow{b} と \overrightarrow{c} は線形独立であることと、 N_b - N_a と N_c - N_a の少なくとも一方は 0 でないことから、
\overrightarrow{ \mathrm{OX}_n } \ne \overrightarrow{ 0 }すなわち Xn は原点 O 上に存在しません。
これは N_b が最小の場合も N_c が最小の場合も同様に成り立つので、Xn が原点 O に存在するための必要十分条件は
N_a = N_b = N_c
であることがわかりました。
あとは N_a,N_b,N_c の正体が何なのかを明らかにする必要がありますが、 N_a は「表が出た場合のうち、それ以前の裏の回数が３で割り切れるものの数」です。ちょっとわかりにくいですが、コイン一投目で表が出た場合は一投目以前の裏の回数は０なのでカウントします。一投目から裏、裏、裏、表と出たときの４投目も、裏の数が３で３の倍数なのでカウントします。一投目、二投目とも表が出たときの二投目も裏の数が０なのでカウントしますが、一投目が裏でが裏で二投目が表の場合の二投目は裏の数が１で３の倍数でないため、カウントしません。
同様に N_b は「表が出た場合のうち、それ以前の裏の回数が３で割って１余るものの数」、 N_c は「表が出た場合のうち、それ以前の裏の回数が３で割って２余るものの数」です。明らかに
N_a + N_b + N_c
は表が出た数の総数です。
このことをもう少し「数学っぽく」表現します。 n 以下の自然数のうち、コイントスして表が出た回の集合を Hn と表記します。また非負整数 km を、コインを m 回投げたときに裏が出た回数と定義します。このとき
\begin{aligned}
A_n =\{m \in H_n | k_m \equiv 0 \mod 3 \} \\
B_n =\{m \in H_n | k_m \equiv 1 \mod 3 \} \\
C_n =\{m \in H_n | k_m \equiv 2 \mod 3 \} \\
\end{aligned}と定義し、
\begin{aligned}
N_a = \# A_n \\
N_b = \# B_n \\
N_c = \# C_n \\
\end{aligned}と定義します。ここに、有限集合S に対して #S を S の要素数と定義します。
このとき
\overrightarrow{ \mathrm{OX}_n } = N_{a}\overrightarrow{a} + N_{b}\overrightarrow{b} + N_{c} \overrightarrow{c} が成り立ち、Xn が原点 O に存在するための必要十分条件は
N_a = N_b = N_c
が成り立つことです。
Na = Nb = Nc ならば Na+Nb+Nc は３の倍数なので、Xn が原点 O に存在するならば表が出た回数は３の倍数です。