確率漸化式の素朴な問題（Mathlog新機能実験）

202

この記事の目標

次の問題を解きます。出典は覚えていないのですが，以前友人に出題されたことのある問題です。しかも状況がかなり分かりやすいので，有名問題かもしれません。

和と積が

3

の倍数になる確率は？

$n$ を正の整数とする。 $1$ つのさいころを $n$ 回投げ，出た目の積を $X_{n}$ ，出た目の和を $Y_{n}$ とする。
⑴　 $X_{n} \equiv 0 (\mod 3)$ となる確率 $p_{n}$ を求めよ。
⑵　 $Y_{n} \equiv 0 (\mod 3)$ となる確率 $q_{n}$ を求めよ。
⑶　 $X_{n} \equiv 0 (\mod 3)$ かつ $Y_{n} \equiv 0 (\mod 3)$ となる確率 $r_{n}$ を求めよ。

以下，この問題に $2$ 通りの答案を与えていきます。

分からないなら文字で置けばいいじゃない？

僕は，わからないものは文字で置きまくれば幸せになれるという思考の持ち主です。そのため，大量に文字を置きつつ答案を作っていきます。

以下，合同式は法を3としたものを考えているものとします。

⑴の解答

$1 - p_{n}$ は， $n$ 回投げて出た目がすべて3の倍数でない確率に等しいから， $1 - p_{n} = {(\frac{4}{6})}^{n}, つまり， p_{n} = 1 - {(\frac{2}{3})}^{n}$

⑵の解答

$Y_{n} \equiv 1$ となる確率を $a_{n}$ ， $Y_{n} \equiv 2$ となる確率を $b_{n}$ とする。このとき $n ≧ 2$ に対して，

$Y_{n - 1} \equiv 0$ のとき， $n$ 回目は3または6が出ればよい。
$Y_{n - 1} \equiv 1$ のとき， $n$ 回目は2または5が出ればよい。
$Y_{n - 1} \equiv 2$ のとき， $n$ 回目は1または4が出ればよい。

つまり，確率遷移図は次のようになる。（ただし矢印は $\frac{1}{3}$ を表す。）
$q_{n} q_{n + 1} a_{n} a_{n + 1} b_{n} b_{n + 1}$

よって， $q_{n} = \frac{1}{3} q_{n - 1} + \frac{1}{3} a_{n - 1} + \frac{1}{3} b_{n - 1} = \frac{1}{3} (q_{n - 1} + a_{n - 1} + b_{n - 1}) = \frac{1}{3}$ である。（ $n ≧ 2$ ）

また， $n = 1$ のときは $q_{1} = \frac{1}{3}$ であるから，すべての自然数 $n$ について $q_{n} = \frac{1}{3}$

（同様に， $a_{n} = b_{n} = \frac{1}{3}$ もすべての自然数 $n$ について成り立つ。）

⑶の解答

次のように記号を定める：

$X_{n} \equiv 0$ かつ $Y_{n} \equiv 0$ となる確率を $r_{n}$ （ $r_{1} = \frac{1}{3}$ ）
$X_{n} \equiv 0$ かつ $Y_{n} \equiv 1$ となる確率を $c_{n}$ （ $c_{1} = 0$ ）
$X_{n} \equiv 0$ かつ $Y_{n} \equiv 2$ となる確率を $d_{n}$ （ $d_{1} = 0$ ）
$X_{n} ≢ 0$ かつ $Y_{n} \equiv 0$ となる確率を $e_{n}$ （ $e_{1} = 0$ ）
$X_{n} ≢ 0$ かつ $Y_{n} \equiv 1$ となる確率を $f_{n}$ （ $f_{1} = \frac{1}{3}$ ）
$X_{n} ≢ 0$ かつ $Y_{n} \equiv 2$ となる確率を $g_{n}$ （ $g_{1} = \frac{1}{3}$ ）

このとき， $r_{n}, c_{n}, d_{n}, e_{n}, f_{n}, g_{n}$ における確率遷移図は右図のようになる。（ただし，矢印はすべて $\frac{1}{3}$ を表している。）

$r_{n} r_{n + 1} c_{n} c_{n + 1} d_{n} d_{n + 1} e_{n} e_{n + 1} f_{n} f_{n + 1} g_{n} g_{n + 1}$
数式で表すと，以下の通り。 ${\begin{cases} r_{n + 1} = \frac{1}{3} r_{n} + \frac{1}{3} c_{n} + \frac{1}{3} d_{n} + \frac{1}{3} e_{n} & \dots \dots ① \\ c_{n + 1} = \frac{1}{3} r_{n} + \frac{1}{3} c_{n} + \frac{1}{3} d_{n} + \frac{1}{3} f_{n} & \dots \dots ② \\ d_{n + 1} = \frac{1}{3} r_{n} + \frac{1}{3} c_{n} + \frac{1}{3} d_{n} + \frac{1}{3} g_{n} & \dots \dots ③ \\ e_{n + 1} = \frac{1}{3} f_{n} + \frac{1}{3} g_{n} & \dots \dots ④ \\ f_{n + 1} = \frac{1}{3} e_{n} + \frac{1}{3} g_{n} & \dots \dots ⑤ \\ g_{n + 1} = \frac{1}{3} e_{n} + \frac{1}{3} f_{n} & \dots \dots ⑥ \end{cases}$

また，

$r_{n} + e_{n} = (Y_{n} \equiv 0 となる確率) = q_{n} = \frac{1}{3} \dots \dots$ ⑦
$c_{n} + f_{n} = (Y_{n} \equiv 1 となる確率) = a_{n} = \frac{1}{3} \dots \dots$ ⑧
$d_{n} + g_{n} = (Y_{n} \equiv 2 となる確率) = b_{n} = \frac{1}{3} \dots \dots$ ⑨

である。さらに，数列 ${f_{n} - g_{n}}$ について，⑤と⑥より， $f_{1} - g_{1} = 0, f_{n + 1} - g_{n + 1} = - \frac{1}{3} (f_{n} - g_{n})$
であるため，すべての自然数 $n$ について $f_{n} - g_{n} = 0$ であり， $f_{n} = g_{n}$ である。特に⑧⑨より， $c_{n} = d_{n}$ である。よって，①②は，④～⑨及び $c_{n} = d_{n}$ を代入することで，①については， $\begin{aligned} r_{n + 1} = \frac{1}{3} r_{n} + \frac{1}{3} c_{n} + \frac{1}{3} c_{n} + \frac{1}{3} (\frac{1}{3} - r_{n}) \\ ∴ & r_{n + 1} = \frac{2}{3} c_{n} + \frac{1}{9} . \end{aligned}$
②については， $\begin{aligned} c_{n + 1} = \frac{1}{3} r_{n} + \frac{1}{3} c_{n} + \frac{1}{3} c_{n} + \frac{1}{3} (\frac{1}{3} - c_{n}) \\ ∴ & c_{n + 1} = \frac{1}{3} r_{n} + \frac{1}{3} c_{n} + \frac{1}{9} . \end{aligned}$
と変形できる。この二式を用いて数列 ${r_{n}}$ の一般項を求めよう。 $r_{n + 1} = \frac{2}{3} c_{n} + \frac{1}{9}$ より $r_{n + 2} = \frac{2}{3} c_{n + 1} + \frac{1}{9}$ だから， $\frac{3}{2} (r_{n + 2} - \frac{1}{9}) = \frac{1}{3} r_{n} + \frac{1}{3} \cdot \frac{3}{2} (r_{n + 1} - \frac{1}{9}) + \frac{1}{9}$
整理すると， $r_{n + 2} - \frac{1}{3} r_{n + 1} - \frac{2}{9} r_{n} = \frac{4}{27} \dots \dots ♠$
ここで， $r_{n} - \frac{1}{3} = s_{n}$ とおくと， $s_{1} = 0, s_{2} = - \frac{2}{9}$ であり， $♠$ は $s_{n + 2} - \frac{1}{3} s_{n + 1} - \frac{2}{9} s_{n} = 0$
である。方程式 $x^{2} - \frac{1}{3} x - \frac{2}{9} = 0$ の異なる2解を $α, β (α < β)$ として， $s_{n + 2} - α s_{n + 1} = β (s_{n + 1} - α s_{n})$
と変形できる。よって数列 ${s_{n + 1} - α s_{n}}$ は，初項 $- \frac{2}{9}$ ，公比 $β$ の等比数列なので，$$
s_{n+1}-\alpha s_n=-\bunsuu29\beta^{n-1}\quad\cdots\cdots\style{font-family:inherit}{\text{⑩}}
$$
同様に，$$
s_{n+2}-\beta s_{n+1}=\alpha(s_{n+1}-\beta s_n)
$$
と変形できるから，数列 ${s_{n + 1} - β s_{n}}$ は，初項 $- \frac{2}{9}$ ，公比 $α$ の等比数列より，$$
s_{n+1}-\beta s_n=-\bunsuu29\alpha^{n-1}\quad\cdots\cdots\style{font-family:inherit}{\text{⑪}}
$$
⑩⑪より，$$
s_n=-\bunsuu2{9(\beta-\alpha)}(\beta^{n-1}-\alpha^{n-1})=-\bunsuu{2}{9}\left{\left(\bunsuu23\right)^{n-1}-\left(-\bunsuu{1}{3}\right)^{n-1}\right}

\therefore\quad \bm{r_n=\bunsuu13-\bunsuu29\left{\left(\bunsuu23\right)^{n-1}-\left(-\bunsuu13\right)^{n-1}\right}}
$$

⑶の別解を模索する

さすがに先ほどの解答の⑶は，模範的な解答ではないと思います。（自然な発想ではあるんですけどね。。。）

ということで，⑶の解答を，最短距離を目指した別解を提示します。

⑶の短い解答

⑴⑵で用いた $p_{n}, q_{n}$ を用いると， $r_{n}$ について， $r_{n + 1} = \frac{1}{3} r_{n} + \frac{1}{3} (p_{n} - r_{n}) + \frac{1}{3} (y_{n} - r_{n})$
という関係式が成り立つ。すなわち， $r_{n + 1} = - \frac{1}{3} r_{n} - \frac{1}{3} {(\frac{2}{3})}^{n} + \frac{4}{9} \dots \dots (#)$
この $(#)$ を変形すると， $r_{n + 1} + \frac{1}{3} {(\frac{2}{3})}^{n + 1} - \frac{1}{3} = - \frac{1}{3} {r_{n} + \frac{1}{3} {(\frac{2}{3})}^{n} - \frac{1}{3}}$
となるため，数列 ${r_{n} + \frac{1}{3} {(\frac{2}{3})}^{n} - \frac{1}{3}}$ は公比 $- \frac{1}{3}$ で初項は（頑張って計算すれば） $\frac{2}{9}$ の等比数列である。すなわち， $r_{n} + \frac{1}{3} {(\frac{2}{3})}^{n} - \frac{1}{3} = \frac{2}{9} {(- \frac{1}{3})}^{n - 1}$
$∴ r_{n} = \frac{1}{3} - \frac{1}{3} \cdot {(\frac{2}{3})}^{n} - \frac{2}{3} \cdot {(- \frac{1}{3})}^{n}$