確率漸化式の難問 – 2020年京大 特色入試 数学 第2問
2020年京大 特色入試 数学 第2問 はサイコロ確率漸化式の問題です。漸化式を立てて極限を求めるという、良くある問題構成ですが、立式にえらく難儀します。問題文は以下のとおりです。
次の3つのルール(i), (ii), (iii) にしたがって三角形 ABC の頂点上でコマを動かすことを考える。
(i) 時刻0においてコマは頂点 A に位置している。
(ii) 時刻0にサイコロを振り、出た目が偶数なら時刻1で頂点 B に、出た目が奇数なら時刻1で頂点 C にコマを移動させる。
(iii) n = 1,2,3, \cdots に対して、時刻 n にサイコロを振り、出た目が3の倍数でなければ時刻 n + 1 でコマを時刻 n – 1 に位置していた頂点に移動させ、出た目が3の倍数であれば時刻 n + 1 でコマを時刻 n -1 にも時刻 n にも位置していなかった頂点に移動させる。
時刻 n においてコマが頂点 A に位置する確率を pn とする。以下の設問に答えよ。
(1) p2,p3 を求めよ。
(2) n = 1,2,3, \cdots に対して pn+1 を pn-1 と pn を用いて表せ。
(3) 極限値 \displaystyle\lim_{ n \to \infty} p_n を求めよ。
問題文が何を言っているのかわかりませんが、まずは小問1で理解を深めましょう。
小問1の解法
求める確率はコマが頂点 A にいる確率ですが、頂点 A にいない時の確率も計算に必要なので、時刻 n ( n = 0,1,2,… )のときに △ABC の各頂点にいる確率をそれぞれ、 A_n, B_n ,C_n と置くことにします。 p_n = A_n です。当然、
0 \leqq A_n,B_n,C_n \leqq 1 \\ A_n + B_n + C_n = 1
が成り立ちます。また、
A_0 =1,B_0=C_0 =0 \\
A_1=0,B_1=C_1 = \frac{1}2です。
以上の準備のもとに、まず A_2,B_2,C_2 を求めます。
n =2 のときにコマが頂点 A にいるための条件は、
- n=1 のときに出た目が3の倍数でない
なので、その確率は \displaystyle\frac{2}3 です。
また、 n =2 のときにコマが頂点 B にいるための条件は、
- n=1 のときにコマが頂点 C にいて、かつ出た目が3の倍数
なので、その確率は \displaystyle\frac{1}3 C_1 = \frac{1}6 です。
同様に、 n =2 のときにコマが頂点 C にいるための条件は、
- n=1 のときにコマが頂点 B にいて、かつ出た目が3の倍数
なので、その確率は \displaystyle\frac{1}3 B_1 = \frac{1}6 です。
以上を表にまとめると、以下のとおりです。
| n | 0 | 1 | 2 |
|---|---|---|---|
| An | 1 | 0 | \frac{2}3 |
| Bn | 0 | \frac{1}2 | \frac{1}6 |
| Cn | 0 | \frac{1}2 | \frac{1}6 |
次に、 A_3,B_3,C_3 を求めます。
n =3 のときにコマが頂点 A にいるための条件は、
- n=2 のときにコマが頂点 B にいて、出た目が3の倍数
- n=2 のときにコマが頂点 C にいて、出た目が3の倍数
のいずれかです。 n=2 のときにコマが頂点 A にいる場合、 A1 = 0 なので、どんな目が出ても頂点 A に遷移しません。
よってその確率は \displaystyle\frac{1}3 B_2 + \frac{1}3 C_2 = \frac{1}9 です。
ゆえに、
p_2 = \frac{2}3,p_3= \frac{1}9です。
小問2の解法
サイコロを振るたび、コマは必ず遷移する
サイコロを振るたび、コマは必ず遷移します。もしそうでないなら、問題文の条件iiiで出た目が3の倍数のとき、遷移先が一意に決定できなくなってしまうので、そんなことはないと予想できますが、以下にそれを証明します。
数学的帰納法で証明します。 n=1 のときは題意から明らかです。 n= 2 のときは小問1で見たように、やはり遷移します。
n ≦ k (k ≧ 2 ) までの範囲で、コマが必ず遷移したと仮定します。 n = k のときのコマの位置が頂点 A の場合、仮定より n = k – 1 のときのコマの位置は頂点 B か頂点 C のいずれかです。ここでサイコロを振った目が3の倍数でないとき、遷移先は一つ前の位置である頂点 B か頂点 C のいずれかです。また、出た目が3の倍数のとき、現在地である頂点 A は遷移先に含まれないので、出た目が何であっても頂点 A 以外に遷移することがわかりました。
同様に、コマの位置が頂点 B や頂点 C の場合も、別の頂点に遷移します。ゆえに、サイコロを振るたび、コマは必ず遷移することが証明できました。
コマの遷移パターンを整理する
サイコロを振るたびコマは必ず遷移するので、時刻 n + 1 にコマが頂点 A にいる場合の遷移パターンは、
- A → B → A
- A → C → A
- B → C → A
- C → B → A
の4種類です。
この情報から漸化式を組み立てればよいのですが、時刻 n +1 における状態を決定するには、2つ前までの時刻の情報が必要です。ところが、それらを決定するには更に2つ遡る必要があるので、結局、時刻0からのすべての情報が必要になってきます。
本当に漸化式が導出できるのか、不安になってきますが、ここで、時刻 n – 1 においてコマが頂点 A にいるとき、時刻 n にはコマは 100% の確率で頂点 B または頂点 C にいることに着目します。
頂点 B と頂点C のどちらに遷移するのかを気にしなければ、時刻 n -2 以前の情報は不要です。そこで、頂点 B と頂点 C をセットで考えます。すると遷移パターンは以下のように整理できます。
- A → B+C → A
- B+C → B+C → A
よって、A → B+C → A と遷移する確率を p(A → B+C → A) 、 B+C → B+C → A と遷移する確率を p(B+C → B+C → A) と表記するとき、時刻 n + 1 においてコマが頂点 A に存在する確率 An+1 は
\begin{aligned}
A_{n+1} = & p( \mathrm{A} \to \mathrm{B+C} \to \mathrm{A}) \\
&+ p( \mathrm{B+C} \to \mathrm{B+C} \to \mathrm{A})
\end{aligned}となります。
p(A → B+C → A) を求める
上に述べたとおり、時刻 n – 1 においてコマが頂点 A にいるとき、時刻 n にはコマは 100% の確率で頂点 B または頂点 C にいるので、その確率 p(A → B+C) は
\begin{aligned}
p( \mathrm{A} \to \mathrm{B+C} ) =A_{n-1}
\end{aligned}です。
この状態から時刻 n + 1 に頂点 A に遷移する確率は出た目が3の倍数でない確率の \frac{2}3 なので、 A → B+C → A と遷移する確率 p(A → B+C → A) は
\begin{aligned}
p( \mathrm{A} \to \mathrm{B+C} \to \mathrm{A}) & =\frac{2}3 p( \mathrm{A} \to \mathrm{B+C} )\\
& = \frac{2}3 A_{n-1}
\end{aligned}です。
p(B+C → B+C → A) を求める
時刻 n においてコマが頂点 B または頂点 C にあるとき、その確率 Bn + Cn は頂点 A から頂点 B または頂点 C に遷移してくる確率 p(A → B+C) と、頂点 B または頂点 C から頂点 B または頂点 C に遷移してくる（すなわち B → C または C →B のたすき掛け遷移）確率 p(B+C → B+C) の和です。
\begin{aligned}
B_{n}+ C_n = & p( \mathrm{A} \to \mathrm{B+C} ) \\
&+ p( \mathrm{B+C} \to \mathrm{B+C})
\end{aligned}一方、先に見たように
\begin{aligned}
p( \mathrm{A} \to \mathrm{B+C} ) =A_{n-1}
\end{aligned}であり、また、
B_n + C_n = 1 - A_n
なので、
\begin{aligned}
p( \mathrm{B+C} \to \mathrm{B+C}) = & B_n+C_n \\
& -p( \mathrm{A} \to \mathrm{B+C} ) \\
= & 1 - A_n -A_{n-1}
\end{aligned}が成り立ちます。p(B+C → B+C) を時刻 n -2 以前の情報を用いずに表現することが出来ました。
B+C → B+C と遷移してきた後で頂点 A に遷移するためには、出た目が3の倍数である必要があるので、
\begin{aligned}
p( \mathrm{B+C} \to \mathrm{B+C} \to \mathrm{A}) = & \frac{1}3p( \mathrm{B+C} \to \mathrm{B+C}) \\
= & \frac{1}3(1 - A_n -A_{n-1})
\end{aligned}です。
pn の漸化式を求める
以上の結果により、
\begin{aligned}
A_{n+1} = & p( \mathrm{A} \to \mathrm{B+C} \to \mathrm{A}) \\
&+ p( \mathrm{B+C} \to \mathrm{B+C} \to \mathrm{A}) \\
= & - \frac{1}3 A_n + \frac{1}3 A_{n-1} + \frac{1}3
\end{aligned}です。
pn = An なので、
\begin{aligned}
p_{n+1} = - \frac{1}3 p_n + \frac{1}3 p_{n-1} + \frac{1}3
\end{aligned}であることがわかりました。
小問3の解法
小問2で得た漸化式を以下のように変形します。
\begin{aligned}
p_{n+1}- \frac{1}3 + \frac{1}3 (p_n - \frac{1}3) - \frac{1}3 (p_{n-1} - \frac{1}3 ) = 0
\end{aligned}ここで q_n = p_n - \displaystyle\frac{1}3 と置くと、
q_{n+1} + \frac{1}3 q_n - \frac{1}3 q_{n-1} = 0と、普通の3項漸化式が得られます。これは一般項を導出できそうです。
セオリー通り、二次方程式
x^2 + \frac{1}3 x - \frac{1}3 = 0の2つの解を α、β ( α < β ) と置きます。
\begin{aligned}
\alpha = & \frac{-1 - \sqrt{13}}{6} \\
\beta = & \frac{-1 + \sqrt{13}}{6} \\
\end{aligned}です。
このとき、
q_{n+1} - \alpha q_n -\beta ( q_n - \alpha q_{n-1}) = 0なので、
q_{n+1} - \alpha q_n = \beta^n ( q_1 - \alpha q_{0}) が成り立ちます。
同様に、
q_{n+1} - \beta q_n = \alpha^n ( q_1 - \beta q_{0}) が成り立ちます。
それぞれの式の両辺に β , α を掛けて辺々引きます。
\begin{matrix}
&\beta q_{n+1} & - \alpha \beta q_n & = &\beta^{n+1} ( q_1 - \alpha q_{0}) \\
- \bigl ) & \alpha q_{n+1} & - \alpha \beta q_n & = &\alpha^{n+1} ( q_1 - \beta q_{0}) \\
\hline
& \beta q_{n+1} & & = & \beta^{n+1} ( q_1 - \alpha q_{0}) \\
& - \alpha q_{n+1}& & &- \alpha^{n+1} ( q_1 - \beta q_{0})
\end{matrix}よって
q_n = \frac{\beta^n(q_1 -\alpha q_0) - \alpha^n(q_1-\beta q_0)}{\beta - \alpha}です。
|α| < 1, |β| < 1 なので、
\lim_{n \to \infty} q_n = 0です。ゆえに
\lim_{n \to \infty} p_n = \frac{1}3です。
解法のポイント
本問には頂点A,B,Cのそれぞれにコマがある確率という、3種類の情報が有ります。このような問題の場合、それぞれを数列と考えて連立漸化式を立てるというのが、ひとつのセオリーです。本問の難しいところは、時刻 n の情報を決定しようと思ったら、時刻0からのすべての情報が必要になってしまう点です。
本問の場合、頂点 B と頂点 C をひとまとめにすることによって、「過去のしがらみ」を断ち切ることが出来ました。 {An},{Bn},{Cn} の3数列というスキームを一旦決めてしまうと、そこから抜け出すことはなかなか難しいですが、どんな条件があれば（あるいは無ければ）式が立てられるのか、という逆算思考を使って、柔軟に局面を打開するようにしましょう。