2001年東大 数学 第6問 はコイントスの場合の数に関する問題です。3つの小問で構成され、最初の2つは文系と共通です。
その2つも結構難しいですが、まだ何とかなります。問題は期待値を求める小問3で、相当な難問です。こいつに拘泥するととんでもないことになるので、第6問は小問1,2だけつまみ食いして、あとは他の問題に時間を費やすのが正しい戦略でしょう。
問題文は以下のとおりで、東大2次試験からの引用です。
コインを投げる試行の結果によって，数直線上にある 2 点 A，B を次のように動かす。
表が出た場合：点 A の座標が点 B の座標より大きいときは， A と B を共に正の方向に 1 動かす。そうでないときは， A のみ正の方向に 1 動かす。
裏が出た場合：点 B の座標が点 A の座標より大きいときは， A と B を共に正の方向に 1 動かす。そうでないときは， B のみ正の方向に 1 動かす。
最初 2 点 A，B は原点にあるものとし，上記の試行を n 回繰り返して A と B を動かしていった結果，A, B の到達した点の座標をそれぞれ a, b とする。
(1) n 回コインを投げたときの表裏の出方の場合の数 2n 通りのうち，a = b となる場合の数を Xn とおく。Xn+1 と Xn の間の関係式を求めよ。
(2) Xn を求めよ。
(3) n 回コインを投げたときの表裏の出方の場合の数 2n 通りについての a の値の平均を求めよ。
問題のシチュエーションはコイントスの結果に応じて A,B が右側に進んでいくという、じゃんけんグリコ風ゲームですが、表が出たらAが進み、裏が出たらBが進むと言った一般的なルールでないところがいやらしいです。
それでは見ていきましょう。なお、本稿の内容は東大が発表したものではありません。
2001年東大 数学 第6問 小問1の解法
n+1 回目のコイントスで a = b となる条件は、
- n 回目で a=b+1 になっていて、かつ n+1 回目のコイントスで裏が出る
- n 回目で b=a+1 になっていて、かつ n+1 回目のコイントスで表が出る
のいずれかです。
n 回目で b=a+1 である場合の数を求めるには、 n 回目で a と b の差が2以上になる場合の数を求める必要があります。そこで、 n=3 のときにいくつになるか計算してみます。
ところが、 n=3 のときの a,b のパターンに a と b の差が2以上になるパターンは出てきません。
| コインの出方 | a | b |
|---|---|---|
| 表-表-表 | 3 | 2 |
| 表-表-裏 | 2 | 2 |
| 表-裏-表 | 2 | 1 |
| 表-裏-裏 | 1 | 2 |
| 裏-表-表 | 2 | 1 |
| 裏-表-裏 | 1 | 2 |
| 裏-裏-表 | 2 | 2 |
| 裏-裏-裏 | 2 | 3 |
よく考えてみるとこれは当然で、a=b+1 のときに表が出たら a も b も１足すので、a と b の差は１のままです。 b=a+1 のときも同様です。
これは大きい発見です。 a>b なら a=b+1 、 b>a なら b=a+1 で、 a と b の大小関係には a=b,a>b,a<b の３種類しかないのですから、
\begin{aligned}
Y_n = & n\text{回コインを投げたとき} \\
&a> b \text{となる場合の数} \\
Z_n = & n\text{回コインを投げたとき} \\
&b> a \text{となる場合の数} \\
p_n = & n\text{回コインを投げたとき} \\
&a= b \text{となる確率} \\
= &\frac{X_n}{2^n} \\
q_n = & n\text{回コインを投げたとき} \\
&a > b \text{となる確率} \\
= &\frac{Y_n}{2^n} \\
r_n = & n\text{回コインを投げたとき} \\
&a < b \text{となる確率} \\
= &\frac{Z_n}{2^n}
\end{aligned}と置くとき、
pn + qn + rn = 1
であり、
\begin{aligned}
p_{n+1} = &n \text{回目で} a> b \text{でかつ} \\
& n+1 \text{回目に裏が出る確率} \\
+ & n \text{回目で} b> a \text{でかつ} \\
& n+1 \text{回目に表が出る確率} \\
= & \frac{1}2 q_n +\frac{1}2 r_n \\
= & \frac{1}2 ( 1 -p_n)
\end{aligned}です。
ゆえに
Xn+1 = 2n – Xn
です。
2001年東大 数学 第6問 小問2の解法
Xn の漸化式より pn の漸化式のほうが一般項を求めやすいので、そちらで計算します。
p_{n+1} = \frac{1}2(1-p_n)なので、
\begin{aligned}
p_{n+1} - \frac{1}3 = & -\frac{1}2 \left(p_n - \frac{1}3 \right) \\
= & \left(-\frac{1}2 \right) ^n \left(p_1 - \frac{1}3 \right) \\
\end{aligned}ですが、1回目のコイントスでは a=1,b=0 か a=0,b=1 のいずれかなので X1 =0 であり、したがって p1=0 です。よって n ≧ 2 のとき
\begin{aligned}
p_n = & \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} \\
\end{aligned}です。これは n=1 のときも成り立ちます。
ゆえに
X_n =\frac{2^n}3+\frac{2}3(-1)^nです。
2001年東大 数学 第6問 小問3の解法
こいつは難問です。 a の期待値 En を出すには a = m である確率 Pn,m が必要ですが、そんなものは小問1にも小問2にも出てこないし、どこにもヒントがありません。小問3で初めて、自力でひねり出す必要があります。
小問3が捨て問である理由がこれです。こいつを求めるのがえらく大変です。
コイントス n+1 回で a = m になる確率は
\begin{aligned}
& n\text{回のコイントスで} a =m \text{かつ} a \geqq b \text{かつ} \\
& n+1\text{回目のコイントスが裏である確率} \\
+& n\text{回のコイントスで} a =m-1 \text{かつ} a < b \\
& \text{かつ}n+1\text{回目のコイントスが} \\
& \text{裏である確率} \\
+& n\text{回のコイントスで} a =m-1 \text{かつ}\\
& n+1\text{回目のコイントスが表である確率} \\
\end{aligned} です。すなわち漸化式を立てるには a,b の大小を考慮する必要があるので、
pn,m = コイントス n 回目で a=m かつ a=b である確率
qn,m = コイントス n 回目で a=m かつ a>b である確率
rn,m = コイントス n 回目で a=m かつ a<b である確率
と置くとき、
\begin{aligned}
P_{n,m} = & p_{n,m}+q_{n,m}+r_{n,m} \\
p_n = &\sum_{m=0}^np_{n,m} \\
q_n = &\sum_{m=0}^nq_{n,m} \\
r_n = &\sum_{m=0}^nr_{n,m} \\
\end{aligned}です。さらにaとbの値の決まり方はコインの表か裏かだけの違いのみであって完全に対称なので
qn,m = rn,m
qn = rn
です。
したがって
\begin{aligned}
P_{n+1,m} = & \frac{1}2(p_{n,m}+q_{n,m}) +\frac{1}2r_{n,m-1} +\frac{1}2 P_{n,m-1} \\
= & \frac{1}2P_{n,m} - \frac{1}2r_{n,m} +\frac{1}2r_{n,m-1} +\frac{1}2 P_{n,m-1}
\end{aligned}ですが、 Pn,m だけの式にならない上に n だけではなく m も減ってしまうので、 Pn,m の一般項が求められるような漸化式を導出するのは大変そうです。
式の中で m を固定できないのであれば、もしかしたら期待値 En で考えれば m が現れないので、漸化式がうまく立てられるかもしれません。
\begin{aligned}
E_{n+1} = & \sum_{m=1}^{n+1} m P_{n+1,m} \\
= &(n+1) P_{n+1,n+1} + \sum_{m=1}^{n} m P_{n+1,m} \\
= &(n+1) P_{n+1,n+1} \\
&+ \sum_{m=1}^{n} m (\frac{1}2P_{n,m} - \frac{1}2r_{n,m} \\
& \text{ }+\frac{1}2r_{n,m-1} +\frac{1}2 P_{n,m-1} ) \\
= &(n+1) P_{n+1,n+1} \\
& +\frac{1}2 \sum_{m =1}^n mP_{n,m} -\frac{1}2 \sum_{m =1}^n mr_{n,m} \\
& +\frac{1}2 \sum_{m =1}^n mr_{n,m-1} +\frac{1}2 \sum_{m =1}^n mP_{n,m-1} \\
= &(n+1) P_{n+1,n+1} \\
& +\frac{1}2 \sum_{m =1}^n mP_{n,m} -\frac{1}2 \sum_{m =1}^n mr_{n,m} \\
& +\frac{1}2 \sum_{m =0}^{n-1} (m+1)r_{n,m} \\
&+\frac{1}2 \sum_{m =0}^{n-1} (m+1)P_{n,m} \\
= &(n+1) P_{n+1,n+1} \\
& +\frac{1}2 E_n-\frac{1}2 nr_{n,n} \\
& +\frac{1}2 \sum_{m =0}^{n-1} r_{n,m} +\frac{1}2 \sum_{m =0}^{n} (m+1)P_{n,m} \\
& - \frac{1}2(n+1) P_{n,n} \\
= &(n+1) P_{n+1,n+1} \\
& +E_n-\frac{1}2 (n+1)r_{n,n} \\
& +\frac{1}2 \sum_{m =0}^{n} r_{n,m} +\frac{1}2 \sum_{m =0}^{n} P_{n,m} \\
& - \frac{1}2(n+1) P_{n,n} \\
= &(n+1) P_{n+1,n+1} \\
& +E_n-\frac{1}2 (n+1)r_{n,n} \\
& +\frac{1}2 r_n +\frac{1}2 \sum_{m =0}^{n} P_{n,m} - \frac{1}2(n+1) P_{n,n} \\
\end{aligned}といい感じに変形できましたが、コインをn 回投げて a=n ということはすべて表が出たということなので、
P_{n,n} = \frac{1}{2^n}です。また明らかに
\sum_{m=0}^n P_{n,m} = 1です。
小問2の結果より
\begin{aligned}
p_n = \frac{1}3 +\frac{2}3 \left (-\frac{1}2 \right)^{n} \\
\end{aligned}であることと qn = rn であることから、
\begin{aligned}
r_n = & \frac{1- p_n}2 \\
= & \frac{1}3 - \frac{1}3 \left ( -\frac{1}2 \right)^n
\end{aligned}です。さらに、コインを n 回投げて a=n のときに b > a ということはありえないので rn,n = 0 です。したがって、
\begin{aligned}
E_{n+1}
= &(n+1) P_{n+1,n+1} \\
& +E_n-\frac{1}2 (n+1)r_{n,n} \\
& +\frac{1}2 r_n +\frac{1}2 \sum_{m =0}^{n} P_{n,m} - \frac{1}2(n+1) P_{n,n} \\
= & \frac{n+1}{2^{n+1}} + E_n \\
& + \frac{1}6- \frac{1}6 \left( -\frac{1}2 \right)^n +\frac{1}2-\frac{n+1}{2^{n+1}} \\
= & E_n + \frac{2}3+ \frac{1}3 \left( -\frac{1}2 \right)^{n+1}
\end{aligned}です。見事に漸化式を導出できました。
よって n ≧ 2 のとき
\begin{aligned}
E_n = & E_1 + \frac{2(n-1 )}3 + \frac{1}{12}\cdot \frac{1- (-\frac{1}2)^{n-1}}{1 + \frac{1}2} \\
= & E_1 + \frac{2(n-1) }3 +\frac{1}{18} \left\{1- \left( -\frac{1}2 \right)^{n-1} \right \} \\
= & E_1 + \frac{2n}3 -\frac{11}{18} + \frac{1}9\left ( -\frac{1}2\right)^n
\end{aligned}ですが
E_1 = \frac{1}2なので
\begin{aligned}
E_n
= \frac{2n}3 -\frac{1}{9} + \frac{1}9\left ( -\frac{1}2\right)^n
\end{aligned}です。これは n= 1 のときも成り立ちます。
解法のポイント
小問1は a と b の差が最大1であることに気がつければ、容易に解けると思います。手堅く得点しましょう。
小問2は小問1ができれば、あとは計算するだけです。
やはり曲者は小問3です。a の期待値を求めろというのに a の各値の確率がわからないのですから、難易度は相当高めです。
本稿で示したように、期待値それ自体で漸化式を立てよう思いつくことがポイントです。もともとのお題が期待値の算出であるというのもヒントではありますが、確率の算出が a の値 m が定まらないことで進退窮まっているということを逆手に取って、それを考えなくて良い手法に飛躍できるかがポイントです。
何かが障害になっているときは、それをうまくバイパスできないか、考えてみましょう。