(4) 漸化式の利用

1から5の数字を独立にn個選んで並べたn桁の数が、3の倍数になる確率の問題。

mod 3 の観点から、漸化式を立てて考えるのが最も考えやすい。 即ち、n桁の数が mod 3 で、0、1、2 になる場合に分けて、 各々の確率を p_n、q_n、r_n とし、 n–1桁の p_n–1、q_n–1、r_n–1 と 関連づけ、p_n = p_n–1 の式 となる漸化式を導く。 そうすれば簡単に解ける。ここで、 p_n + q_n + r_n = 1 は、忘れず活用する。

１×２の横長方形格子を、左下の原点から出発し、毎時刻等確率で隣の格子点に移動する点が、
時刻 n で x=0 上にある確率の問題。

時刻 n で、x=0、x=1、x=2 となる確率を各々 p_n、q_n、r_n として漸化式を導き、それを解く。 ここでも、p_n + q_n + r_n = 1 には気をつける。 p_n+1 = x p_n + yⁿ⁺¹ の形の漸化式が出てくる。 この漸化式は、確率の問題でよく登場するので、すぐに解けるようにしておく。

x₀ = 12 から 始め、表で0との中点、裏で1との中点に移動するとき、 x_n < 23 となる確率の問題。

漸化式を使う。そのために状態の場合分けが必要である。 どのように場合分けするのがよいか、問題は直接示唆していないので 検討してみる。

求める確率の条件は、x_n < 23 で、逆算してその一つ前で裏が出る場合は x_n–1 + 12 < 23 、 即ち x_n–1 < 13 となり、 13 も重要な境界 になることがわかる。 0 < x_n ≦ 13、 13 ≦ x_n < 23、 23 ≦ x_n < 1 で場合分けして、問題の条件分岐と 適合するか調べてみる。その結果、うまく適合するのでこの場合分けを 採用する。このように、漸化式を利用する問題の中には、 適切な場合分けを自分で推測して検証しなければならない上級問題がある。
　あとは漸化式を解くだけである。

三角形の頂点を移動する２点が、同じ頂点から初めてn時刻後にまた同じ頂点にいる確率の問題。

漸化式を利用するための場合分けは難しくない。 この問題では、３頂点の区別は必要ないので、 同じ頂点にいる場合と、別の頂点にいる場合に分ければよい。 導かれる漸化式も簡単である。

y₁=サイコロの目、 y_n = サイコロの目 + 1y_n–1 のとき、 1+√32 ≦ y_n ≦ 1+√3 となる確率の問題。

これも"上級の問題"である。 なぜ 1+√32 と 1+√3 が出てくるのか？　状況がわかりづらい問題である。まずは小さな n で 状況を調べて見る。そうするとすぐ気づくのは、求める確率の条件を満たすには n回目のサイコロの目は1か2であることが必要である。目が1のとき、問3と同様、 逆算して 1+√32 ≦ 1 + 1y_n–1 を 解くと、y_n–1 ≦ 1+√3 が出てくる。これで上記の"なぜ"の部分が わかった。そして漸化式を利用するため、 0 < y_n < 1+√32、 1+√32 ≦ y_n ≦ 1 + √3、 1 + √3 < y_n と場合分けすればよいと推測される。 この場合分けにしたがって漸化式を立ててみる。あとは簡単に解ける。

n車両を赤、青、黄で塗る。隣り合った車両のどちらかが赤になる塗り方の場合の数の問題。

漸化式で考えるとわかりやすい。n車両からn+1車両に増やすことを考える。 ここで重要なのは、n+1車両で条件を満たすなら、n車両でも条件を満たしている ということである。そして、n車両から最後に１車両追加してn+1車両にするとき、 n車両目が赤か否かで状況が変わることである。 以上をふまえて、n車両目が赤で条件を満たす場合 (r_n) とn車両名が赤以外で 条件を満たす場合 (x_n) に分けて漸化式を立てる。これは簡単にできる

この問題の連立漸化式を一つの数列に整理する (x_n を消去する) と、 r_n+1、r_n、r_n–1 の3項間の漸化式になる。 この漸化式も確率問題でよく登場するので、すぐに解けるようにしておくこと。

n回サイコロをふった目の和が mod 5 で k となる確率 (p_n(k))とその極限の問題。

(1) は、問題が示唆する場合わ、即ち mod 5 の値での場合わをふまえて考えればよい。 その場合わの中で、一つの場合だけ繰り上がりで値が重複することに気をつける (例えば p_n(0) のときの 4 mod 5 の場合、4 + 1 ≡ 4 + 6 ≡ 0 mod 5)。

(2) では、(イ) は簡単な計算から、(ロ) は (1) の結果を使って、すぐ出てくる。

(3) では、(2) の (ロ) を使うと M_n – m_n ≦ 16(M_n+1 – m_n+1) が成り立つことがわかる。この簡単な事実に気づけるかどうかが ポイントである。この結果と (2) の (イ) を使うと、 極限がすぐわかる。随所にヒントが散りばめられた問題である。

A、B、Cがそれぞれ赤、白、青の札を持つ。サイコロが3の倍数でAとBが交換、 そうでないときAとCが交換で、n回目にAが赤をもっている確率の問題。

(1) では、赤札をAが持つ場合、Bが持つ場合、Cが持つ場合に場合分けして 漸化式を立てるように指示されている。簡単である。

(2) では、(1) で求めた漸化式を解く。a_n + b_n + c_n = 1 も忘れずに使う。a_n だけの式にすると、一つとびの漸化式 (a_n+1 = a_n–1の式) になるところだけが特徴的である。 "a_n+1 = a_nの式" の場合と同様に解いて、n の奇遇で 場合分けすればよい。

最初に白玉N個、赤玉3個で、一個取り出し白玉を戻す試行。n回目に赤玉を取り出す確率の問題。

(1) では、問題の指示にしたがって、残っている赤玉が1個、2個、3個で場合分けする。 問題の意図が若干わかりにくいが、P_{1, n}、P_{2, n}、P_{3, n} を異なった数列とし、それらを含む3つの漸化式を導いて問題を解くことを示唆している。

(2) では、求める P_n = P_{1, n} + P_{2, n} + P_{3, n} で、(1) の結果を使うと、P_{n + 1} と P_n を結びつける 漸化式がうまく現れる。あとは、それを解くだけで、これは難しくない。 Nは定数であることに注意する (変数と勘違いして混乱しないように)。