ryu.です。
前回の確率漸化式の続きの記事になります。後半はさらに難易度の高い問題が続きますが、頑張ってついてきてください。
標準問題１
サイコロを\(n\)回投げ、\(k\)回目に出た目を\(a_k\)とする。また、\(s_n\)を\(\displaystyle \sum_{k=1} ^{n} 10^{n-k}a_k\)とする。
(1) \(s_n\)が4で割り切れる確率を求めよ。
(2) \(s_n\)が6で割り切れる確率を求めよ。
(3) \(s_n\)が7で割り切れる確率を求めよ。
さて一発目は一橋大学の整数関連の問題から。ぱっと見は確率漸化式を用いる問題に見えないのがさらに厄介なポイントである。それでは解いていこう。
まずは問題文中の式や状況についてまずは考察していく。この式を見るに、１〜６の６種類の数字を用いて\(n\)桁の数字を、サイコロを振ることで上の位から作っていくことになるのがわかると良いかと思う。これを利用して問題を解いていこう。一部整数の内容も入ってくる。
まずは(1)。整数が４の倍数である時は下２桁のみが関連しているので、ここのみを考えれば解くことができる。また、一応確認として、それまで\(n-2\)回目までに振ったサイコロの目とは無関係に、独立して目が出るのだからこの2回のみを考えれば良いことになる。すなわち、下２桁が４の倍数となるので、計36通りのうち12、16、24、32、36、44、52、56、64の９通りが条件を満たす数になってくる。したがって、どの数字が作られる確率も等しいと考えられるから、求める確率は\(\displaystyle\frac{9}{36}=\frac{1}{4}\)となる。これは比較的楽か。
続いては(2)。ここから３の倍数であることも考えると数全体の桁の数値が必要になってくる。すると、それぞれの位の数が３で割った余りと照らし合わせていくことを考えるのだが、普通に考えてそれはかなり莫大な労力を要する。したがって、ある桁までの結果に応じてさらに一つ桁を多くすることでその確率の変化を捉えていくことが思いつけば良いか。（多分ここが難しい）
ここでまず\(n≥2\)を考えると、\(s_{n-1}\)を６で割った余りが０、１、２、３、４、５であった時にその一つ下の位に数字をつけて６の倍数となるようにすることを考えると、それぞれ６、２、４、６、２、４を付ければ良いことになる。すなわち、前の位の数字に関わらず\(\displaystyle\frac{1}{6}\)で６の倍数にすることができるというわけだ。したがって、\(s_{n-1}\)を6で割った余りは０から５のみであるので求める確率は常に\(\displaystyle\frac{1}{6}\)である。これは明らかに\(n=1\)の時にも成立することから、その答えで良いということになる。ここの結論が意外にシンプルなので解けた時には面食らうかもしれないが、よくよく考えてみれば至極妥当な結論であると言えよう。
そして最後、(3)である。同じように考えていくが、今回は７であるため少し勝手が違ってくる。今回は7で割った余りは０から６までであるのだが\(s_{n-1}\)の余りと一桁足した時にどの数字を加えれば良いかは右の図Iで示している。どの数字を足すかに関しては余りが０の時はどれでもいけず、それ以外では\(\displaystyle\frac{1}{6}\)で余りが０にできる。したがって漸化式は下のように立式できる（ただし\(n≥2\)）。
$$p_n = \frac{1}{6}(1- p_{n-1} )$$
あとはこれを解いていけば良い。なお、\(p_1 = 0\)である。この漸化式を変形して、
$$p_n -\frac{1}{7} = -\frac{1}{6}\left(p_{n-1} – \frac{1}{7}\right)$$
となる。すなわち、数列\(\displaystyle\{ p_n – \frac{1}{7} \}\)は初項 \(\displaystyle p_1-\frac{1}{7} = -\frac{1}{7}\)、公比\(\displaystyle -\frac{1}{6}\)の等比数列と考えられるため、求める確率は
$$p_n = \frac{1}{7} -\frac{1}{7} \left( -\frac{1}{6}\right)^{n-1}$$
である。
標準問題２
四角形の４つの頂点に１、２、３、４と時計回りに番号がつけられている。時刻0において、この四角形の頂点１と頂点３の上をそれぞれ１つずつの粒子が占めているものとし、頂点２と頂点４の上には粒子は存在しないものとする（図１）。その後、１秒毎に、存在する粒子の中で最小の番号の頂点上を占める粒子が確率\(\displaystyle\frac{1}{2}\)で消滅し、確率\(\displaystyle\frac{1}{4}\)ずつで隣り合う二つの頂点のいずれかへ移動する。ただし、移動した頂点上をすでに他の粒子が占めている場合は、その粒子と合体して１つの粒子となる。以下、\(m,n\)を自然数とする。時刻\(n\)秒において、この四角形の４つの頂点のうち１つの頂点にのみ粒子が存在する確率を\(P_n\)で表し、４つの頂点のいずれの上にも粒子が存在しない確率を\(Q_n\)で表す。
(1) \(P_2,Q_2\)を求めよ。
(2) \(P_{2m-1},P_{2m},Q_{2m-1},Q_{2m}\)をそれぞれ求めよ。
続いては、こちらの問題。慶應大学で出題された問題だが、同大学の医学部には確率漸化式を題材にした問題がほぼ確定で出てくるので、ここを志望校にしている人は要注意だ。現実的にはかなりありえない様な状況設定だが、落ち着いて状況の遷移を考えて整理していこう。話はそこからである。
では(1)を進めつつそれを考えていこう。まず一手目は頂点1にある粒子が移動ないし消滅するが、その後、粒子が二つ隣り合って存在する時には一つになるか対角線上に移動するかとなる。すなわち、この移動の法則性を考えると、二つ存在する時には\(n\)が奇数の時には対角線上に存在し、\(n\)が偶数の時には隣り合う頂点に存在することになる。あと粒子数が1個ないし0個であった時には簡単なので具体的に書かないが。これを表すと右の遷移図の様になる。
これを利用して求めていくと、
$$ P_2 = \frac{1}{2} \times \frac{1}{2} + \frac{1}{2} \times \frac{3}{4} = \frac{5}{8}$$
$$Q_2 = \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$$
となる。これは正直前座の様なものだが、本題である漸化式を立てていこう。偶数主体で考えていくと、偶数秒で2個存在している場合を\(D_{2m}\)とおいておくと、
$$ D_{2(m+1)} = \frac{1}{8} D_{2m} $$
$$ P_{2(m+1)} = \frac{5}{8} D_{2m} + \frac{1}{4} P_{2m} $$
$$ Q_{2(m+1)} = \frac{1}{4} D_{2m} + \frac{3}{4} P_{2m} + Q_{2m}$$
の三式が立てられるので、あとはこれを解いていこう。
まずは\(D_{2m}\)。これは簡単に求められることだろう。\(\frac{1}{8}\)の繰り返しなので、$$D_{2m} = \biggl( \frac{1}{8} \biggr) ^ m$$であることは容易に判断できるはずだ。この流れで\(P_{2m}\)を解いていこう。\(D_{2m}\)を代入して整理してみると、
$$ P_{2(m+1)} = \frac{5}{8} \biggl( \frac{1}{8} \biggr) ^ m + \frac{1}{4} P_{2m} $$
となる。これに\(8^m P_{2m} = R_{2m}\)とみなすと、新たな漸化式
$$ \frac{1}{8} R_{2(m+1)} = \frac{5}{8} + \frac{1}{4} R_{2m} $$
というえげつなくシンプルなものが現れてくる。後はこれを解いていくと、まずは変形して
$$ R_{2(m+1)} + 5 = 2 ( R_{2m} + 5 ) $$
となるから、数列\( \{ R_{2m} +5 \}\)は初項\(10\)、公比\(2\)の等比数列であることから、
$$ R_{2m} = 5 ･ 2^m -5 $$
となる。後はこれを元に戻して、
$$ P_{2m} = \frac{5}{4^m} – \frac{5}{8^m} $$
と求めることができよう。最後の\(Q_n\)に関しては全体から今までの二つを引けば良いだけなので、実は先の漸化式を解く必要はない。したがって、
$$ Q_{2m} = 1 – \frac{5}{4^m} + \frac{4}{8^m} $$
と求められる。後はこれに奇数の場合を足していく。したがって、残りの処理は
$$ P_{2m-1} = \frac{1}{2} (D_{2m-2} + P_{2m-2}) = \frac{5}{2･4^{m-1}} – \frac{2}{8^{m-1}} $$
$$ Q_{2m-1} = \frac{1}{2}P_{2m-2} + Q_{2m-2} = 1- \frac{5}{2･4^{m-1}} + \frac{3}{2･8^{m-1}} $$
となる。ここまでが答えだ。偶奇で処理するタイプの確率漸化式の問題は出題数はそれなりにある上、かなり計算処理が面倒になるケースが多い。そのため、ここで少し練習するいい機会になったかと思う。
標準問題３
サイコロを\(n\)回投げて出た目を順に\(X_1,X_2, ･･･,X_n\)とする。さらに、
$$ Y_1 = X_1 , Y_k = X_k + \frac{1}{Y_{k-1}}$$
によって\(Y_1 , Y_2 , ･･･,Y_n\)を定める。$$\frac{1+\sqrt{3}}{2} ≤ Y_n ≤ 1+\sqrt{3}$$となる確率\(p_n\)を求めよ。
それでは、確率漸化式系列の最後の砦として京都大学の問題を二つおいておこう。 この問題、ぱっと見は予想がつきにくい上に厄介そうな見た目をしているが、一つ一つ整理して実験していこう。まずは\(Y_k\)の式について見ていくが、これを展開して現れる二つの項のうち、\(X_k\)の方は実際のサイコロの目であるから整数である。さらに\(Y_{k-1}\)が問題文中の範囲を満たしている場合に、その逆数の取りうる範囲は
$$ \frac{1}{1+\sqrt{3}}=\frac{\sqrt{3}-1}{2} ≤ \frac{1}{Y_{k-1}} ≤ \sqrt{3}-1 = \frac{2}{1+\sqrt{3}}$$
と考えられる。これを数直線にして図示してみると右の図のようになる。この数直線を考えると、逆数にしたときに入っている範囲にサイコロの目の数（\(X_k\)）を加えることを考えると、取りうる値は１か２のいずれかしかあり得ない。範囲のどこにいてもこれには関係なく、３以上になることもあり得ない。
それでは逆にこの範囲に入っていない場合はどうか。まずはこの漸化式を考えると、\(X_k ≥ 1\)、\(Y_{k-1} ≥ 0\)であることが言えるので（実際には帰納的にでも証明はしておくことを推奨する）、\(Y_k ≥ 1\)が言える。これを適用するとすべての自然数についてこれが言えることもわかるであろう。したがって、上の状況に入っていない中で考えるべき範囲は、
$$ 1 ≤ Y_{k-1} ≤ \frac{1+\sqrt{3}}{2}, Y_{k-1} ≥ 1+\sqrt{3}$$
の２種類となることが右の図から言える。したがって、逆数にしたときに出てくる範囲は図のような限られた範囲となる。前者の範囲（緑）の場合、次に範囲に入る時は１のみが許容される。同様にして後者の範囲（黄色）の場合、次に範囲に入る場合は２のみが許容される。つまり、どっちの場合においても許容されている確率は\(\displaystyle\frac{1}{6}\)である。これは\(n=k-1\)において\(p_{n-1}\)に含まれていない全場合になるので、ここから確率漸化式を立てていくことができるであろう。
すると、ここからは\(n\)を用いた議論に戻していくが、\(p_{n-1}\)だったときには\(\displaystyle\frac{1}{3}\)、\(1-p_{n-1}\)だったときには\(\displaystyle\frac{1}{6}\)で\(p_n\)を満たすので、この遷移図により漸化式を立てていくと、
$$ p_n = \frac{1}{3} p_{n-1} + \frac{1}{6} (1- p_{n-1}) = \frac{1}{6} p_{n-1} + \frac{1}{6}$$
という式が立てられる。ここからはここまでついてこれている人ならば安牌であろう。この式を変形して、
$$ p_n – \frac{1}{5} = \frac{1}{6} \left( p_{n-1} – \frac{1}{5} \right) $$
となることから、あとはこれを解いて（ここからの過程は端折らせてもらうが）、
$$ p_n = \frac{1}{5} – \frac{1}{5} \left( \frac{1}{6} \right)^n $$
と求められる。考え方こそ難しかったが、結論は意外にシンプルである。
発展問題
次の３つのルールに従って三角形\(ABC\)の頂点上でコマを動かすことを考える。
(ⅰ) 時刻\(0\)においてコマは頂点\(A\)に位置している。
(ⅱ) 時刻\(0\)にサイコロを振り、出た目が偶数なら時刻\(1\)に頂点\(B\)に、出た目が奇数なら時刻\(1\)に頂点\(C\)にコマを移動させる。
(ⅲ) \(n=1,2,3,\)⋯に対して、時刻\(n\)にサイコロを振り、出た目が\(3\)の倍数でなければ時刻\(n+1\)でコマを時刻\(n−1\)に位置していた頂点に移動させ、出た目が\(3\)の倍数であれば時刻\(n+1\)でコマを時刻\(n−1\)にも時刻\(n\)にも位置していなかった頂点に移動させる。
時刻\(n\)においてコマが頂点\(A\)に位置する確率を\(p_n\)とする。
(1) \(p_2, p_3\)を求めよ。
(2) \(n=1,2,3,\)⋯に対して\(p_{n+1}\)を\(p_{n-1}\)と\(p_n\)を用いて表せ。
(3) 極限値\(\displaystyle \lim_{n \to \infty} p_n\)を求めよ。（文系用：\(p_n\)を求めよ。）
最後は京大の直近の特色入試から一問。難易度としては京大のこの形式にしては平易である様な気もするが、如何せん難易度は高いのが事実。誘導が無ければ正答率が激減することだろう。ひとつ一つしっかりと状況を整理して問題を見ていこう。基本的にやることは変わらない。
ともあれまずは(1)。始めの方なので、ひとつひとつ丁寧に書き出していけば問題ない。まず１秒目にはそれぞれ確率\(\displaystyle\frac{1}{2}\)でBもしくはCへ移動する。さらにその後だが、Bへ移動した場合にはその後Aへ確率\(\frac{2}{3}\)で移動し、残りの確率でCへ移動する。逆にCへ移動した場合にはその後Aへ\(\displaystyle\frac{2}{3}\)で移動し、残りの確率でBへ移動する。したがって、\(p_2\)は、
$$\frac{1}{2}\times\frac{2}{3}\times 2= \frac{2}{3}$$
と求められる。さらに、もう一度考えると、２秒目にAにいる時はどの様に移動させてもAへ３秒目に行かないので端折って考える。逆にBにいる時は、この秒数だと必ずCを経由してからの移動になるので、Aへ戻ってくる確率は\(\displaystyle\frac{1}{3}\)になる。これと同じ様な議論をすると、求める確率\(p_3\)は、
$$ \frac{1}{2}\times\frac{1}{3}\times\frac{1}{3}\times 2=\frac{1}{9}$$
である。
続いて、(2)。ここが肝になってくる。問題文の指示にもある通り、3回の間の遷移を考えないといけないからだ。
まずは\(n-1,n,n+1\)回目の間を考えていくが、\(n+1\)回目でAにくる時はまず\(n\)回目では必ずA以外の場所にいなければならない。その上で、\(n-1\)回目にどこにいたかを考えていくが、ここでAにいた時には\(n\)秒目には必ずA以外の頂点に移動し、その後\(\displaystyle\frac{2}{3}\)の確率でAの方へ移動する。（３の倍数でなければ良いため）逆に\(n-1\)回目と\(n\)回目でA以外にいた時は\(\displaystyle\frac{1}{3}\)でAへ移動できる。この２パターンを合計すると\(1-p_n\)として表せることになる。詳しい遷移に関してはこの図を見て欲しい。したがって求める漸化式は
$$ p_{n+1} = \frac{2}{3}p_{n-1} + \frac{1}{3} (1-p_n – p_{n-1})\\
= \frac{1}{3} \bigl( 1 – p_n + p_{n-1} \bigr)$$
となる。ここからは漸化式を解いていくだけだ。
その中で(3)を解いてみよう。単純に三項間漸化式なのだが、定数項が邪魔なのでこいつを処理しておこう。\(\displaystyle q_n = p_n -\frac{1}{3}\)とおいておくことで、上の漸化式が
$$ q_{n+1}= \frac{1}{3} \bigl( – q_n + q_{n-1} \bigr)$$
と変形することができるので、特性方程式より\(\displaystyle q=\frac{-1±\sqrt{13}}{6}\)が解としてあげられるので、これを小さい順に\(\alpha, \beta\)とおいておくと、これをそれぞれ2通りに変形して、
$$ q_{n+1} – \alpha q_n = \beta (q_n – \alpha q_{n-1}) \\
q_{n+1} – \beta q_n = \alpha (q_n – \beta q_{n-1})$$
となるので、これを解いていくと、
$$ 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) $$
となる。ここで、それぞれの式の右辺において\(\alpha, \beta\)の絶対値が１より小さいことからどちらも収束する。したがって、
$$ ( \beta – \alpha ) q_n = {\beta}^n (q_1 – \alpha q_0) – {\alpha}^n (q_1 – \beta q_0) $$
であるから、\(\displaystyle \lim_{n \to \infty} q_n = 0\)となることが言える。したがって、元の式へ展開していって、\(\displaystyle \lim_{n \to \infty} p_n = \frac{1}{3}\)と求められるということだ。なお、実際の\(p_n\)もここから同じ様にして求められる。計算過程は端折らせてもらうが、
$$ p_n = \frac{1}{\sqrt{13}} \left\{ \frac{\sqrt{13}-2}{3} \left(\frac{-1+\sqrt{13}}{6}\right)^n + \frac{\sqrt{13}+2}{3} \left(\frac{-1-\sqrt{13}}{6}\right)^n \right\} + \frac{1}{3}$$
となれば問題ない。また、極限を求める方に関しては三角不等式を使った賢いやり方があるので、最後にそちらだけ紹介しておく。
$$ |q_n| = \frac{1}{|\beta-\alpha|}|\beta q_n – \alpha q_n| ~~~~~~~~~\\
= \frac{1}{|\beta-\alpha|}|q_{n+1} – \alpha q_n – q_{n+1} + \beta q_n| ~~~\\
≤ \frac{1}{|\beta-\alpha|}(|q_{n+1} – \alpha q_n| + |q_{n+1} – \beta q_n|) $$
と変形することができるので、0に収束するという事実とはさみうちの定理から\( \displaystyle \lim_{n \to \infty} q_n = 0\)が言えるので同じ様に持っていくことができる。
以上になります。今回の記事では最後のほうにはかなり難易度の高い問題が集結していましたが、もちろん他にも難しい問題がありますので、この記事で何か発見などがあればそれを生かしつつ新たな知識を吸収していってもらいたいです。
コメント