東大のじゃんけん問題を3人から4人に変えたらすごかった

オリジナルの問題

1971年の東大で、3人でじゃんけんをしてk回目に1人の勝者が決まる確率を問われる問題が出されたのだとか。

3人でも2人でもあいこの確率は$${\frac{1}{3}}$$であることを利用すると簡単とのこと。k回目のじゃんけんをする前に3人残っていて1人が勝利する場合と、k回目のじゃんけんをする前に2人残っていて1人が勝利する場合が考えられる。

前者はk-1回目まであいこが続く確率が$${(\frac{1}{3})^{k-1}}$$、3人中1人が勝つ確率が$${\frac{1}{3}}$$、乗算して$${(\frac{1}{3})^k}$$

後者は1からk-1回目までのどこかで1回だけ、3人中2人が勝つので$${(k-1) \times \frac{1}{3}}$$、k-1回から2人が勝つ1回を除いたk-2回はあいこが続く。3人でも2人でもあいこの確率は同じなので$${(\frac{1}{3})^{k-2}}$$。2人のうち1人が勝つ確率が$${\frac{2}{3}}$$。乗算して$${\frac{2(k-1)}{3^k}}$$

前者と後者を加算して$${\frac{2k-1}{3^k}}$$

よせばいいのに研究心が芽生えた

オリジナルの問題は、3人と2人とであいこの確率は同じだから簡単に解けた。では4人でじゃんけんしたらどうなるんだろう？ よせばいいのに、そんな疑問が浮かんでしまった。浮かんでしまったなら、計算するしかない。

さすがに近道はなさそう

4人では計算を簡単にする余地がなさそうなので、k回目に2～4人残っている確率を求めてからk+1回目に1人の勝者が出るような確率を求める方針で、地道に計算していく。もはや確率の問題というより、漸化式、計算の正確さ、根性。そういった問題の様相を呈している。

定義と立式

k回目のじゃんけんを終えて1人の勝者が出る確率を$${P_k}$$、4人が残っている確率を$${a_k}$$、3人が残っている確率を$${b_k}$$、 2人が残っている確率を$${c_k}$$とする。 するとk+1回目に1人の勝者が決まる確率$${P_{k+1}}$$は、$${P_{k+1}=\frac{4}{27}a_k+\frac{1}{3}b_k+\frac{2}{3}c_k}$$となる。

k回目のじゃんけんを終えて４人残っている確率

k回目に4人が残っている確率$${a_k}$$は簡単。4人であいこがひたすら続く確率なので、$${a_k=(\frac{13}{27})^k}$$

k回目のじゃんけんを終えて3人残っている確率

3人が残っている確率は確率漸化式で。 k+1回目に3人が残っている確率$${b_{k+1}}$$は、k回目までに4人が残っていてk+1回目で4人中3人が残る確率と、k回目までに3人が残っていてk+1回目であいことなる確率との和なので、

$$
\begin{array}{}b_{k+1}&=&\frac{4}{27}a_k+\frac{1}{3}b_k\\3^{k+1}b_{k+1}-3^kb_k&=&\frac{4}{27}\times (\frac{13}{27})^k\times3^{k+1}\\\ &=&\frac{4}{9}\times(\frac{13}{9})^{k}\end{array}\\\ 3^kb_kを階差数列として一般項を求めると、\\\begin{array}{} 3^kb_k &=& 3^1b_1+\frac{4}{9}\times\frac{13}{9}\sum_{j=1}^{k-1} (\frac{13}{9})^{j-1}\\\ &=& 3\times\frac{4}{27}+\frac{52}{81}\times\frac{(\frac{13}{9})^{k-1}-1}{\frac{13}{9}-1} \\\ &=& \frac{4}{9}+\frac{52}{81}\times\frac{9}{4}\times(\frac{13}{9})^{k-1}-1)\\\ &=&(\frac{13}{9})^{k}-1\\\
b_k&=&\frac{1}{3^k}((\frac{13}{9})^k-1)
\end{array}
$$

k回目のじゃんけんを終えて2人残っている確率

$$
k回目に2人が残っている確率c_kも同様に\\\ \begin{array}{} c_{k+1}&=&\frac{2}{9}a_k+\frac{1}{3}b_k+\frac{1}{3}c_k\\\ &=&\frac{2}{9}\times(\frac{13}{27})^k+\frac{1}{3}\times\frac{1}{3^k}((\frac{13}{9})^k-1)+\frac{1}{3}c_k\\\ 3^{k+1}c_{k+1}-3^kc_k&=&\frac{2}{3}\times(\frac{13}{9})^k+(\frac{13}{9})^k-1\\\ &=&\frac{5}{3}\times(\frac{13}{9})^k-1\\\ 3^kc_k&=&3^1c_1+\frac{5}{3}\times\frac{13}{9}\sum_{j=1}^{k-1} ((\frac{13}{9})^{j-1}-1)\\\ &=&3\times\frac{2}{9}+\frac{65}{27}\times\frac{(\frac{13}{9})^{k-1}-1}{\frac{13}{9}-1}-(k-1)\\\ &=&-k+\frac{5}{3}+\frac{65}{27}\times\frac{9}{4}((\frac{13}{9})^{k-1}-1)\\\ &=&\frac{65}{12}\times(\frac{13}{9})^{k-1}-k+\frac{5\times4-65}{12}\\\ &=&\frac{65}{12}\times(\frac{13}{9})^{k-1}-k-\frac{15}{4}\\\ c_k&=&\frac{1}{3^k}(\frac{65}{12}\times(\frac{13}{9})^{k-1}-k-\frac{15}{4})
\end{array}
$$

材料は揃ったので計算！

$$
\begin{array}{}
当初の式 P_{k+1}&=&\frac{4}{27}a_k+\frac{1}{3}b_k+\frac{2}{3}c_k に代入すると\\
P_{k+1}&=&\frac{4}{27}\times(\frac{13}{27})^k+\frac{1}{3}\times\frac{1}{3^k}((\frac{13}{9})^k-1)+\frac{2}{3}\times\frac{1}{3^k}(\frac{65}{12}\times(\frac{13}{9})^{k-1}-k-\frac{15}{4})\\
&&(\frac{13}{9})^kを作るように変形すると\\
&=&\frac{4}{3^{k+3}}\times(\frac{13}{9})^k+\frac{1}{3^{k+1}}\times(\frac{13}{9})^k-\frac{1}{3^{k+1}}+\frac{2}{3^{k+1}}(\frac{65}{12}\times\frac{9}{13}\times(\frac{13}{9})^k-k-\frac{15}{4})\\
&=&\frac{4}{3^{k+3}}\times(\frac{13}{9})^k+\frac{1}{3^{k+1}}\times(\frac{13}{9})^k-\frac{1}{3^{k+1}}+\frac{5}{2\times3^k}\times(\frac{13}{9})^k+\frac{2}{3^{k+1}}(-k-\frac{15}{4})\\
&=&\frac{(4\times2+1\times2\times3^2+5*3^3)\times(\frac{13}{9})^k}{2\times3^{k+3}}+\frac{2(-k-\frac{15}{4})-1}{3^{k+1}}\\
　　&=&\frac{161}{2\times3^{k+3}}\times(\frac{13}{9})^k+\frac{1}{3^{k+1}}(-2k-\frac{17}{2})\\
P_k&=&\frac{161}{26\times3^k}\times(\frac{13}{9})^k+\frac{1}{3^k}(-2k-\frac{13}{2})\\
　&=&\frac{1}{3^k}(\frac{161}{26}\times(\frac{13}{9})^k-2k-\frac{13}{2})
\end{array}
$$

検算！

$$
では、上で求めたP_kが本当に合っているのか、地道に計算した確率と照らし合わせてみましょう。\\\ P_1は当然\frac{4}{27}になるはず。\\\ \begin{array}{}P_1&=&\frac{1}{3}(\frac{161}{26}\times\frac{13}{9}-2-\frac{13}{2})\\\ &=&\frac{1}{3}\times\frac{161-36-117}{18}=\frac{4}{3\times9}=\frac{4}{27} \end{array}\\\ よし、合ってる。\\
P_2は、\frac{13}{27}\times\frac{4}{27}+\frac{4}{27}\times\frac{1}{3}+\frac{2}{9}\times\frac{2}{3}\\=\frac{52+4\times9+4\times27}{27^2}=\frac{196}{27^2}になるはず。\\\ \begin{array}{}P_2&=&\frac{1}{9}(\frac{161}{26}\times\frac{169}{81}-4-\frac{13}{2})\\\ &=&\frac{1}{9}\times\frac{161\times13-4\times2\times3^4-13\times3^4}{2\times3^4}=\frac{196}{3^6}\end{array}\\\ よし、合ってる。\\P_3まで合ってたら合ってることにしてくれと思いつつ、\\\ \frac{13^2\times4}{27^3}+\frac{13\times4\times1}{27^2\times3}+\frac{13\times2\times2}{27\times9\times3}+\frac{4\times1^2}{27\times3^2}+\frac{4\times1\times2}{27\times3^2}+\frac{2\times1\times2}{9\times3^2}\\=\frac{676+52\times9+52\times27+4\times81+8\times81+4\times243}{27^3}=\frac{4492}{27^3}\\\ ここまで来ると検算用の確率を求めるのも大変だ。\\\ \begin{array}{}P_3&=&\frac{1}{27}(\frac{161\times13^3}{26\times9^3}-6-\frac{13}{2})\\\ &=&\frac{1}{27}\times(\frac{161\times169-6\times2\times9^3-13\times9^3}{2\times9^3})=\frac{4492}{27^3}\end{array}\\\ 合ってる。\\ということでP_k=\frac{1}{3^k}(\frac{161}{26}\times(\frac{13}{9})^k-2k-\frac{13}{2})はおそらく合っているでしょう。
$$