一癖ある確率漸化式 – 2015年東大 数学 第2問
2015年東大 数学 第2問 はおなじみのサイコロ文字列確率問題です。問題文は以下の通りです。
どの目も出る確率が \frac{1}{6} のさいころを1つ用意し、次のように左から順に文字を書く。
さいころを投げ、出た目が1, 2, 3のときは文字列AAを書き、4のときは文字Bを、5のときは文字Cを、6のときは文字Dを書く。さらに繰り返しさいころを投げ、同じ規則に従って、AA, B, C, Dをすでにある文字列の右側につなげて書いていく。
たとえば、さいころを5回投げ、その出た目が順に2, 5, 6, 3, 4であったとすると、得られる文字列は、AACDAABAACDAABとなる。このとき、左から4番目の文字はD、5番目の文字はAである。
(1) n を正の整数とする。 n 回さいころを投げ、文字列を作るとき、文字列の左から n 番目の文字がAとなる確率を求めよ。
(2) n を2以上の整数とする。 n 回さいころを投げ、文字列を作るとき、文字列の左から n-1 番目の文字がAで、かつ n 番目の文字がBとなる確率を求めよ。
この分野の問題としては、一見スタンダードな雰囲気です。割と何とかなりそうな気がしますが、サイコロの出る目によって追加する文字数が違っているというのが、意外に凶悪なギミックです。サイコロを振った数と文字数が連動しなくなるので、複雑な場合分けを要求されそうな予感がします。
小問１の解法
サイコロを振った数と文字の位置が連動しないのは、サイコロの目が1,2,3のときに2文字追加するからです。そこで、1,2,3の目が出る回数で場合分けすれば、文字の位置に関するあいまいさは解消できそうです。
この方向で解けないか、試してみましたが、あまりの面倒くささに筆者は早々にギブアップしました。別の方法を検討してみます。
サイコロを振った数にこだわるのは、確率を計算するのに必須だからですが、ここは発想を変えて、1,2,3の目が出る回数の管理は漸化式に任せることにします。
サイコロを振る回数について
問題文では、「 n 回さいころを投げ、文字列を作るとき、文字列の左から n 番目の文字がAとなる確率」などというように、サイコロを振る回数に言及していますが、サイコロを振る回数が n 回より大きければ何回であっても、 n 番目が特定の文字である確率は同じです。
これから確率漸化式を立式するにあたって、サイコロを振る回数を考慮すると無駄に複雑になるだけなので、以降、十分に多い回数サイコロを振っていることを前提とし、 n 番目の文字が何であるかだけにフィーチャーします。
確率の定義
n 番目の文字が A のとき、 A の出方には2種類あります。すなわち、
- n 文字目のところでサイコロを振って、1,2,3の目が出た場合。 n 文字目の A は AA の1文字目である
- n-1 文字目のところでサイコロを振って、1,2,3の目が出た場合。 n 文字目の A は AA の2文字目である
そこで、 n \geqq 2 のとき、確率 P_n, Q_n, R_n を以下のように定義します。
- P_n = n 文字目のところでサイコロを振って、1,2,3の目が出る確率
- Q_n = n-1 文字目のところでサイコロを振って、1,2,3の目が出る確率
- R_n = n 文字目が A 以外である確率
また、
\begin{aligned}
& P_1 = \frac{1}{2} \\
& Q_1 = 0 \\
& R_1 = \frac{1}{2}
\end{aligned}とします。当然、
\begin{aligned}
P_n +Q_n+ R_n = 1 \\
(n \geqq 1)
\end{aligned}が成り立ちます。
漸化式の立式
P_n, Q_n, R_n の漸化式を立てます。
まず、 P_n について考えます。 n 文字目のところでサイコロが振れるための必要十分条件は、 n-1 文字目のところでサイコロが振れて、かつ 4,5,6 が出るか、 n-2 文字目のところでサイコロが振れて、かつ 1,2,3 が出ることです。
その確率は、
R_{n-1} + Q_{n-1}です。 P_n は n 文字目でサイコロを振って 1,2,3 が出る確率なので、
P_n = \frac{1}{2}(R_{n-1} + Q_{n-1})が成り立ちます。
ところが、
\begin{aligned}
P_n +Q_n+ R_n = 1 \\
(n \geqq 1)
\end{aligned}なので、これを代入して
P_n = \frac{1}{2}(1-P_{n-1} ) \cdots(1)を得ます。
一方 Q_n は、 n-1 文字目のところでサイコロを振って、1,2,3の目が出る確率なので、明らかに
Q_n = P_{n-1} \cdots (2)です。
漸化式を解く
式(1)より、
\begin{aligned}
P_n - \frac{1}{3} = -\frac{1}{2}(P_{n-1} - \frac{1}{3}) \\
(n \geqq 2)
\end{aligned}を得ます。
P_1 = \frac{1}{2} であったので、
\begin{aligned}
& P_n - \frac{1}{3} = \left(-\frac{1}{2} \right )^{n-1}(P_{1} - \frac{1}{3}) \\
& \text{ } = \frac{1}{6} \left(-\frac{1}{2} \right )^{n-1}\\
& \text{ } = -\frac{1}{3} \left(-\frac{1}{2} \right )^{n}\\
& \text{ } (n \geqq 2)
\end{aligned}となり、ここからただちに
\begin{aligned}
& P_n = \frac{1}{3} -\frac{1}{3} \left(-\frac{1}{2} \right )^{n}
\end{aligned}を得ます。上式は n= 1 のときも成り立ちます。
ゆえに、 n 番目の文字が A である確率 P_n + Q_n は、式(2)を適用して
\begin{aligned}
& P_n + Q_n \\
& = P_n + P_{n-1} \\
& = \frac{1}{3} -\frac{1}{3} \left(-\frac{1}{2} \right )^{n} + \frac{1}{3} -\frac{1}{3} \left(-\frac{1}{2} \right )^{n-1} \\
& = \frac{2}{3} -\frac{1}{3} \left(-\frac{1}{2} \right )^{n} + \frac{2}{3} \left(-\frac{1}{2} \right )^{n} \\
& =\frac{2}{3} +\frac{1}{3} \left(-\frac{1}{2} \right )^{n} \\
&(n \geqq 2)
\end{aligned}となります。上式は n = 1 のときも成り立ちます。
小問２の解法
n-1 文字目が A でかつ、 n 文字目でサイコロが振れるための必要十分条件は、 n-1 文字目の A が AA の2文字目であることです。
こうなる確率は Q_{n-1} ですが、式(2) より、
\begin{aligned}
Q_n & = P_{n-1} \\
& = \frac{1}{3} -\frac{1}{3} \left(-\frac{1}{2} \right )^{n-1} \\
& = \frac{1}{3} +\frac{2}{3} \left(-\frac{1}{2} \right )^{n} \\
& \text{ } (n \geqq 2) \\
\end{aligned}が成り立ちます。上式の結果は n=1 のときも成り立ちます。
ゆえに求める確率は、
\begin{aligned}
& \frac{1}{6}Q_{n-1} \\
& = \frac{1}{18} +\frac{1}{9} \left(-\frac{1}{2} \right )^{n-1} \\
& \text{ } (n \geqq 2) \\
\end{aligned}です。
解法のポイントと今後の学習方針
まず、漸化式の立式に持ち込むことが第一です。1,2,3が出る回数の場合分けでも何とか出来るのかもしれませんが、漸化式のほうが簡単だと思います。
次に、漸化式が満たすべき条件が複数あって複雑な場合は、思い切って漸化式も複数立ててみましょう。代数の問題で、不明な値をすべて変数において、連立方程式にするとか、代入して1変数に統合するとかいうのと同じ発想です。
漸化式を複数にしてしまうと、本稿で示したように、意外に簡単に解くことが出来ます。同じ発想で解く問題に「2017年東工大 数学 第4問」がありますので、こちらの記事もご覧ください。
本問のような問題に対処するには、漸化式に関する問題をたくさん解いて、感覚を養うことが必要です。漸化式に確率が絡む場合、確率に関する部分は一般にそれほど難しくないので、確率の問題にこだわる必要はないでしょう。
ググると、漸化式に特化した問題集が見つかるので、そういう本をみっちり学習することは、非常に効果的です。