4

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

158
1
$$\newcommand{bekutoru}[1]{\displaystyle\overrightarrow{\mbox{#1}\phantom{A}\hspace{-1em}}} \newcommand{bm}[1]{\boldsymbol{#1}} \newcommand{bunsuu}[2]{\dfrac{\,#1\,}{\,#2\,}} \newcommand{Deg}[0]{^{\circ}} \newcommand{dsqrt}[1]{\displaystyle\sqrt{\,#1\,}} \newcommand{foo}[1]{\ifnum#12\text{それは2だよ!}\else\text{それは2じゃないよ!}\fi} \newcommand{gauss}[1]{\left[\mkern1mu {#1}\mkern1mu\right]} \newcommand{kaku}[1]{\angle\mbox{#1}} \newcommand{kumiawase}[2]{\mathord{{}_{#1}\kern-.12em{}\text{C}_{#2}}} \newcommand{mdot}[0]{\!\cdot\!} \newcommand{sankaku}[1]{\triangle \mbox{#1}} \newcommand{suuretu}[1]{\left\{#1\right\}} \newcommand{tsqrt}[1]{\textstyle\sqrt{\,#1\,}} \newcommand{zyunretu}[2]{\mathord{{}_{#1}\kern-.12em{}\text{P}_{#2}}} $$

この記事の目標

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

和と積が$3$の倍数になる確率は?

$n$を正の整数とする。$1$つのさいころを$n$回投げ,出た目の積を$X_n$,出た目の和を$Y_n$とする。
⑴ $X_n\equiv 0\pmod3$となる確率$p_n$を求めよ。
⑵ $Y_n\equiv 0\pmod3$となる確率$q_n$を求めよ。
⑶ $X_n\equiv 0\pmod3$かつ$Y_n\equiv 0\pmod3$となる確率$r_n$を求めよ。

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

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

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

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

⑴の解答

$1-p_n$は,$n$回投げて出た目がすべて3の倍数でない確率に等しいから,$$ 1-p_n=\left(\bunsuu46\right)^n,\qquad\style{font-family:inherit}{\text{つまり,}}\qquad \bm{p_n=1-\left(\bunsuu23\right)^n} $$

⑵の解答

$Y_n\equiv 1$となる確率を$a_n$$Y_n\equiv2$となる確率を$b_n$とする。このとき$n\geqq2$に対して,

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

つまり,確率遷移図は次のようになる。(ただし矢印は$\bunsuu13$を表す。)
$$ \xymatrix { *++[o][F-]{q_n\vphantom{b}} \ar[dr] \ar[r]\ar[ddr] & *++[o][F-]{\!\!\rlap{q_{n+1}}\hphantom{a_n}\vphantom{b}\,\,} \\*++[o][F-]{a_n\vphantom{b}} \ar[r]\ar[dr]\ar[ur] & *++[o][F-]{\!\!\rlap{a_{n+1}\vphantom{b}}\hphantom{q_n}\,\,} \\*++[o][F-]{b_n} \ar[r]\ar[ur]\ar[uur] & *++[o][F-]{\!\!\rlap{b_{n+1}}\hphantom{q_n}\,\,} \\ }$$

よって,$q_n=\bunsuu13q_{n-1}+\bunsuu13a_{n-1}+\bunsuu13b_{n-1}=\bunsuu13(q_{n-1}+a_{n-1}+b_{n-1})=\bunsuu13$である。($n\geqq2$

また,$n=1$のときは$q_1=\bunsuu13$であるから,すべての自然数$n$について$\bm{q_n=\bunsuu13}$

(同様に,$a_n=b_n=\bunsuu13$もすべての自然数$n$について成り立つ。)

⑶の解答

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

  • $X_n\equiv0$かつ$Y_n\equiv0$となる確率を$r_n$$r_1=\bunsuu13$
  • $X_n\equiv0$かつ$Y_n\equiv1$となる確率を$c_n$$c_1=0$
  • $X_n\equiv0$かつ$Y_n\equiv2$となる確率を$d_n$$d_1=0$
  • $X_n\not\equiv0$かつ$Y_n\equiv0$となる確率を$e_n$$e_1=0$
  • $X_n\not\equiv0$かつ$Y_n\equiv1$となる確率を$f_n$$f_1=\bunsuu13$
  • $X_n\not\equiv0$かつ$Y_n\equiv2$となる確率を$g_n$$g_1=\bunsuu13$

このとき,$r_n,c_n,d_n,e_n,f_n,g_n$における確率遷移図は右図のようになる。(ただし,矢印はすべて$\bunsuu13$を表している。)

$$ \xymatrix { *++[o][F-]{r_n\vphantom{b}} \ar[dr] \ar[r]\ar[ddr] & *++[o][F-]{\!\!\rlap{r_{n+1}}\hphantom{a_n}\vphantom{b}\,\,} \\*++[o][F-]{c_n\vphantom{b}} \ar[r]\ar[dr]\ar[ur] & *++[o][F-]{\!\!\rlap{c_{n+1}\vphantom{b}}\hphantom{q_n}\,\,} \\*++[o][F-]{d_n} \ar[r]\ar[ur]\ar[uur] & *++[o][F-]{\!\!\rlap{d_{n+1}}\hphantom{q_n}\,\,} \\ *++[o][F-]{e_n\vphantom{b}} \ar[dr] \ar@[blue][uuur]\ar[ddr] & *++[o][F-]{\!\!\rlap{e_{n+1}}\hphantom{a_n}\vphantom{b}\,\,} \\*++[o][F-]{f_n\vphantom{b}} \ar@[blue][uuur]\ar[dr]\ar[ur] & *++[o][F-]{\!\!\rlap{f_{n+1}\vphantom{b}}\hphantom{q_n}\,\,} \\*++[o][F-]{g_n\vphantom{b}} \ar@[blue][uuur]\ar[ur]\ar[uur] & *++[o][F-]{\!\!\rlap{g_{n+1}}\vphantom{b}\hphantom{q_n}\,\,} \\ }$$
数式で表すと,以下の通り。$$ \begin{cases} r_{n+1}=\bunsuu13r_n+\bunsuu13c_n+\bunsuu13d_n+\bunsuu13e_n& \cdots\cdots\style{font-family:inherit}{\text{①}}\\ c_{n+1}=\bunsuu13r_n+\bunsuu13c_n+\bunsuu13d_n+\bunsuu13f_n& \cdots\cdots\style{font-family:inherit}{\text{②}}\\ d_{n+1}=\bunsuu13r_n+\bunsuu13c_n+\bunsuu13d_n+\bunsuu13g_n& \cdots\cdots\style{font-family:inherit}{\text{③}}\\ e_{n+1}=\bunsuu13f_n+\bunsuu13g_n& \cdots\cdots\style{font-family:inherit}{\text{④}}\\ f_{n+1}=\bunsuu13e_n+\bunsuu13g_n& \cdots\cdots\style{font-family:inherit}{\text{⑤}}\\ g_{n+1}=\bunsuu13e_n+\bunsuu13f_n& \cdots\cdots\style{font-family:inherit}{\text{⑥}}\\ \end{cases} $$

また,

  • $r_n+e_n=(Y_n\equiv0\style{font-family:inherit}{\text{となる確率}})=q_n=\bunsuu13\quad \cdots\cdots$
  • $c_n+f_n=(Y_n\equiv1\style{font-family:inherit}{\text{となる確率}})=a_n=\bunsuu13\quad \cdots\cdots$
  • $d_n+g_n=(Y_n\equiv2\style{font-family:inherit}{\text{となる確率}})=b_n=\bunsuu13\quad \cdots\cdots$

である。さらに,数列$\suuretu{f_n-g_n}$について,⑤と⑥より,$$ f_1-g_1=0,\quad f_{n+1}-g_{n+1}=-\bunsuu13\left(f_n-g_n\right) $$
であるため,すべての自然数$n$について$f_n-g_n=0$であり,$f_n=g_n$である。特に⑧⑨より,$c_n=d_n$である。よって,①②は,④~⑨及び$c_n=d_n$を代入することで,①については,$$ \begin{align} &r_{n+1}=\bunsuu13r_n+\bunsuu13c_n+\bunsuu13c_n+\bunsuu13\left(\bunsuu13-r_n\right)\\ \therefore\quad &r_{n+1}=\bunsuu23c_n+\bunsuu19. \end{align} $$
②については,$$ \begin{align} &c_{n+1}=\bunsuu13r_n+\bunsuu13c_n+\bunsuu13c_n+\bunsuu13\left(\bunsuu13-c_n\right)\\ \therefore\quad &c_{n+1}=\bunsuu13r_n+\bunsuu13c_n+\bunsuu19. \end{align} $$
と変形できる。この二式を用いて数列$\suuretu{r_n}$の一般項を求めよう。$r_{n+1}=\bunsuu23c_n+\bunsuu19$より$r_{n+2}=\bunsuu23c_{n+1}+\bunsuu19$だから,$$ \bunsuu32\left(r_{n+2}-\bunsuu19\right)=\bunsuu13r_n+\bunsuu13\cdot\bunsuu32\left(r_{n+1}-\bunsuu19\right)+\bunsuu19$$
整理すると,$$ r_{n+2}-\bunsuu13r_{n+1}-\bunsuu29r_n=\bunsuu4{27}\quad \cdots\cdots\spadesuit $$
ここで,$r_n-\bunsuu13=s_n$とおくと,$s_1=0,s_2=-\bunsuu29$であり,$\spadesuit$$$ s_{n+2}-\bunsuu13s_{n+1}-\bunsuu29s_n=0 $$
である。方程式$x^2-\bunsuu13x-\bunsuu29=0$の異なる2解を$\alpha,\beta\ (\alpha<\beta)$として,$$ s_{n+2}-\alpha s_{n+1}=\beta(s_{n+1}-\alpha s_n) $$
と変形できる。よって数列$\suuretu{s_{n+1}-\alpha s_n}$は,初項$-\bunsuu29$,公比$\beta$の等比数列なので,$$
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)
$$
と変形できるから,数列$\suuretu{s_{n+1}-\beta s_n}$は,初項$-\bunsuu29$,公比$\alpha$の等比数列より,$$
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}=\bunsuu13r_n+\bunsuu13(p_n-r_n)+\bunsuu13(y_n-r_n) $$
という関係式が成り立つ。すなわち,$$ r_{n+1}=-\bunsuu13r_n-\bunsuu13\left(\bunsuu{2}{3}\right)^n+\bunsuu49\qquad\cdots\cdots(\#) $$
この$(\#)$を変形すると,$$ r_{n+1}+\bunsuu13\left(\bunsuu23\right)^{n+1}-\bunsuu13=-\bunsuu13\left\{r_{n}+\bunsuu13\left(\bunsuu23\right)^{n}-\bunsuu13\right\} $$
となるため,数列$\left\{r_{n}+\bunsuu13\left(\bunsuu23\right)^{n}-\bunsuu13\right\}$は公比$-\bunsuu13$で初項は(頑張って計算すれば)$\bunsuu29$の等比数列である。すなわち,$$ \qquad r_{n}+\bunsuu13\left(\bunsuu23\right)^{n}-\bunsuu13=\bunsuu29\left(-\bunsuu13\right)^{n-1} $$
$$ \therefore\quad \bm{r_n=\bunsuu13-\bunsuu13\cdot\left(\bunsuu23\right)^n-\bunsuu23\cdot\left(-\bunsuu13\right)^n} $$

多分これが一番速いと思います。

まとめ

というわけで今回は,問題こそ「和と積が$3$の倍数になる確率は?」と聞かれているだけでしたが,いざ手を動かしてみると難しい問題でした。これ,$\bmod 5$とか$\bmod 7$とかになったら,とんでも大変なことになるんじゃないかな。。。

この問題に対する別解を思いついた方は,コメントを頂けると嬉しいです!

また,新機能としてXypicが実装されましたね。いくつか図を書いてみましたが,いかがでしょうか。コメントいただけると嬉しいです。(ちなみに僕はTikZ派ですので,慣れない記法でしたね。。)

投稿日:20201122

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

ぱるち
ぱるち
125
17447
数学屋さんをしています。代数,数論系に興味があり,今は楕円曲線と戯れています。Mathlogは現実逃避用という噂もあります。@f_d00123

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中