京都大学 理系 2015年度 第6問 解説
問題編
【問題】
2つの関数を
\[
f_0(x) =\frac{x}{2}, \quad f_1(x) = \frac{x+1}{2}
\]とおく。$\displaystyle x_0=\frac{1}{2}$から始め、各$n=1,2,\cdots$ について、それぞれ確率 $\displaystyle \frac{1}{2}$ で $x_n=f_0(x_{n-1})$ または $x_n=f_1(x_{n-1})$ と定める。
このとき、$\displaystyle x_n \lt \frac{2}{3}$ となる確率$P_n$を求めよ。
【考え方】
「$n$回○○したときに××となる確率」というのは、$n$回目と$n+1$回目の関係から確率の漸化式を出し、数列の問題として解くのがオーソドックスなやり方です。今回は$x_n \lt \frac{2}{3}$となる確率を求めるので、こうなるときに$x_{n-1}$がどうなっていないといけないかを考えてみましょう。
もし、$x_n=f_0(x_{n-1})$だった場合、$x_n \lt \frac{2}{3}$となるには、$x_{n-1} \lt \frac{4}{3}$となる必要があります。一方、$x_n=f_1(x_{n-1})$だった場合、$x_n \lt \frac{2}{3}$となるには、$x_{n-1} \lt \frac{1}{3}$となる必要があります。ということは、$x_{n-1}$が$\frac{4}{3}$未満や$\frac{1}{3}$未満になる確率も求めないといけないということです。
ここで、$x_{n-1} \lt \frac{4}{3}$は常に成り立つことがわかります。というのも、$x\lt 1$のとき、$f_0(x),f_1(x) \lt 1$となるからです。問題は$x_{n-1} \lt \frac{1}{3}$の場合です。
もし、$x_n=f_0(x_{n-1})$だった場合、$x_n \lt \frac{1}{3}$となるには、$x_{n-1} \lt \frac{2}{3}$となる必要があります。一方、$x_n=f_1(x_{n-1})$だった場合、$x_n \lt \frac{1}{3}$となるには、$x_{n-1} \lt -\frac{1}{3}$となる必要があります。$x\gt 0$のとき、$f_0(x),f_1(x) \gt 0$なので、2つ目のケースはありえません。1つ目のケースは求めたい確率そのものです。
これらを組み合わせると、$P_n$に関する漸化式ができあがるので、あとはそれを解けばおしまいです。
解答編
【問題】
2つの関数を
\[
f_0(x) =\frac{x}{2}, \quad f_1(x) = \frac{x+1}{2}
\]とおく。$\displaystyle x_0=\frac{1}{2}$から始め、各$n=1,2,\cdots$ について、それぞれ確率 $\displaystyle \frac{1}{2}$ で $x_n=f_0(x_{n-1})$ または $x_n=f_1(x_{n-1})$ と定める。
このとき、$\displaystyle x_n \lt \frac{2}{3}$ となる確率$P_n$を求めよ。
【解答】
$x_n=f_0(x_{n-1})$のとき、
\begin{eqnarray}
x_n \lt \frac{2}{3} \Leftrightarrow \frac{x_{n-1} }{2} \lt \frac{2}{3} \Leftrightarrow x_{n-1} \lt \frac{4}{3} \ \ \cdots (1)
\\[5pt]
x_n \lt \frac{1}{3} \Leftrightarrow \frac{x_{n-1} }{2} \lt \frac{1}{3} \Leftrightarrow x_{n-1} \lt \frac{2}{3} \ \ \cdots (2)
\end{eqnarray}
であり、$x_n=f_1(x_{n-1})$のときは、
\begin{eqnarray}
x_n \lt \frac{2}{3} \Leftrightarrow \frac{x_{n-1}+1}{2} \lt \frac{2}{3} \Leftrightarrow x_{n-1} \lt \frac{1}{3} \ \ \cdots (3)
\\[5pt]
x_n \lt \frac{1}{3} \Leftrightarrow \frac{x_{n-1}+1}{2} \lt \frac{1}{3} \Leftrightarrow x_{n-1} \lt -\frac{1}{3} \ \ \cdots (4)
\end{eqnarray}
となる。
ここで、$0 \lt x \lt 1$のとき、$0 \lt f_0(x),f_1(x) \lt 1$となるのは明らかであり、$0 \lt x_0 \lt 1$なので、0以上のすべての整数$n$について、$0 \lt x_n \lt 1$となる。よって、上の(1)は必ず起こり、(4)が起こることはない。
よって、$x_n \lt \frac{2}{3}$となるのは「$x_n=f_0(x_{n-1})$ または$( x_n=f_1(x_{n-1}) $ かつ $ x_{n-1} \lt \frac{1}{3} )$のとき」であり、$x_n \lt \frac{1}{3}$となるのは、「$x_n=f_0(x_{n-1})$ かつ $ x_{n-1} \lt \frac{2}{3}$のとき」である。
$x_n \lt \frac{1}{3}$ となる確率を$Q_n$とすると、以上の結果から次が成り立つ（$n$は1以上の整数。$P_0,Q_0$はそれぞれ$x_0\lt \frac{2}{3},x_0\lt \frac{1}{3}$となる確率であり、$P_0=1,Q_0=0$である）。
\begin{eqnarray}
P_n &=& \frac{1}{2} + \frac{1}{2}Q_{n-1} \\[5pt]
Q_n &=& \frac{1}{2}P_{n-1}
\end{eqnarray}
これより、0以上の整数$n$について、$P_{n+2} = \frac{1}{2} + \frac{1}{4}P_n$が成り立つことがわかる。
$R_n=P_{2n}(n=0,1,2,\cdots)$とすると、
\begin{eqnarray}
R_{n+1} - \frac{2}{3} &=& \frac{1}{4}\left( R_n - \frac{2}{3} \right) \\[5pt]
R_n - \frac{2}{3} &=& \frac{1}{4^n} \left( R_0 - \frac{2}{3} \right) = \frac{1}{4^n} \left( P_0 - \frac{2}{3} \right) \\[5pt]
R_n &=& \frac{1}{3\cdot 4^n} + \frac{2}{3} \\[5pt]
\end{eqnarray}
となる。よって、
\begin{eqnarray}
P_{2n} &=& \frac{1}{3\cdot 4^n} + \frac{2}{3}
= \frac{1}{3\cdot 2^{2n} } + \frac{2}{3} \\[5pt]
\end{eqnarray}
となる。
$R_n=P_{2n+1}(n=0,1,2,\cdots)$とすると、同様に計算して
\begin{eqnarray}
R_n - \frac{2}{3} &=& \frac{1}{4^n} \left( R_0 - \frac{2}{3} \right) = \frac{1}{4^n} \left( P_1 - \frac{2}{3} \right) \\[5pt]
R_n &=& - \frac{1}{6\cdot 4^n} + \frac{2}{3} \\[5pt]
\end{eqnarray}
となる。よって、
\begin{eqnarray}
P_{2n+1} &=& - \frac{1}{6\cdot 4^n} + \frac{2}{3} = \ - \frac{1}{3\cdot 2^{2n+1} } + \frac{2}{3}
\end{eqnarray}
あわせると、$P_n$は次のように書ける。
\begin{eqnarray}
P_n &=& \frac{1}{3} \left( - \frac{1}{2} \right)^n + \frac{2}{3}
\end{eqnarray}
これが求める答えである。
【解答終】
【解説】
$P_{n+2} = \frac{1}{2} + \frac{1}{4}P_n$となるため、$n$が偶数の場合と奇数の場合で分けて一般項を求めています。最後、答えを一つにまとめましたが、偶数奇数で分けて答えを書いても問題ないでしょう。
さて、上では漸化式を使って確率を求めましたが、直接求める方法も考えてみましょう。
$n=1,2,3$くらいの場合を考えてみます。
$x_1$がとりうる値は、$\displaystyle \frac{1}{4},\frac{3}{4}$でそれぞれ同じ確率。
$x_2$がとりうる値は、$\displaystyle \frac{1}{8},\frac{3}{8},\frac{5}{8},\frac{7}{8}$でそれぞれ同じ確率。
$x_3$がとりうる値は、$\displaystyle \frac{1}{16},\frac{3}{16},\frac{5}{16},\frac{7}{16},\frac{9}{16},\frac{11}{16},\frac{13}{16},\frac{15}{16}$でそれぞれ同じ確率。
こうして見ると、$x_n$の場合、$\displaystyle \frac{2k-1}{2^{n+1} }$でそれぞれ同じ確率になることが予想できます（$k=1,2,\cdots 2^n$）。
この方針で別解を書いてみます。個数を求めるところが結構大変になりますが。
別解編
【問題】
2つの関数を
\[
f_0(x) =\frac{x}{2}, \quad f_1(x) = \frac{x+1}{2}
\]とおく。$\displaystyle x_0=\frac{1}{2}$から始め、各$n=1,2,\cdots$ について、それぞれ確率 $\displaystyle \frac{1}{2}$ で $x_n=f_0(x_{n-1})$ または $x_n=f_1(x_{n-1})$ と定める。
このとき、$\displaystyle x_n \lt \frac{2}{3}$ となる確率$P_n$を求めよ。
【別解】
0以上のすべての$n$について、次の命題Ａが成り立つことを示す。
命題Ａ：$x_n$のとりうる値は、$\displaystyle \frac{2k-1}{2^{n+1} }$である（$k=1,2,\cdots 2^n$）。また、それぞれの値をとる確率は、$\displaystyle \frac{1}{2^n}$である。
(1) $n=0$ のときは明らかに成り立つ。
(2) $n=m$ のときに命題Ａが成り立つとする。
$x_{m+1}=f_0(x_m)$のとき、仮定より、とりうる値は、$\displaystyle \frac{2k-1}{2^{m+2} }$である（$k=1,2,\cdots 2^m$）。
$x_{m+1}=f_1(x_m)$のとき、とりうる値は、$\displaystyle \frac{2k-1+2^m}{2^{m+2} }$である（$k=1,2,\cdots 2^m$）。
よって、$x_{m+1}$がとりうる値は、$\displaystyle \frac{2k-1}{2^{m+2} }$となる（$k=1,2,\cdots 2^{m+1}$）。また、$f_0$と$f_1$で値がかぶることはないので、それぞれの値をとる確率は、$\displaystyle \frac{1}{2^{m+1} }$となる。よって、$n=m+1$のときも命題Ａが成り立つ。
(1)(2)から、0以上のすべての$n$について、命題Ａが成り立つ。
次に、$\displaystyle \frac{2k-1}{2^{n+1} } \lt \frac{2}{3}$となる$k(k=1,2,\cdots 2^n)$の個数を数える。このとき、$k \lt \frac{2^{n+2}+3}{6}$なので、この右辺を超えない最大の整数を求めればよい。
分子が偶数でないもの、3の倍数でないものは整数になりえないので、最大の整数となる候補としては、$\frac{2^{n+2}+2}{6}$か$\frac{2^{n+2}-2}{6}$しかない。$m$を0以上の整数として、$n=2m+1$とかけるとき
\begin{eqnarray}
2^{n+2}-2
=
2^{2m+3}-2
&=&
2(4^{m+1}-1)
=
2\cdot 3 (1+4+\cdots +4^m)
\end{eqnarray}
なので、6の倍数になる。よって、$n$が奇数のときは、$\frac{2^{n+2}-2}{6}$が整数となる。
一方、$n=2m$とかけるときは、
\begin{eqnarray}
2^{n+2}+2
&=&
2^{2m+2}+2
=
2(2\cdot 4^m+1)
=
2\{ 2 (4^m-1) + 3\}
\end{eqnarray}
であり、$(4^m-1)$は上で見たとおり3の倍数なので、$2^{n+2}+2$は6の倍数となる。よって、$n$が偶数のときは、$\frac{2^{n+2}+2}{6}$が整数となる。
それぞれの値をとる確率は$\frac{1}{2^n}$なので、$n$が奇数のときは
\begin{eqnarray}
P_n
&=&
\frac{1}{2^n} \cdot \frac{2^{n+2}-2}{6} \\[5pt]
&=&
\frac{2^2}{6} - \frac{1}{2^n} \cdot \frac{2}{6} \\[5pt]
&=&
\frac{2}{3} - \frac{1}{3\cdot 2^n}
\end{eqnarray}
となり、$n$が偶数のときは
\begin{eqnarray}
P_n
=
\frac{1}{2^n} \cdot \frac{2^{n+2}+2}{6}
=
\frac{2}{3} + \frac{1}{3\cdot 2^n}
\end{eqnarray}
となる。
【別解終】
とりうる値を出すところまではそんなに難しくないですが、そこから個数を計算するところが激しく難しいです。このやり方だと、時間内に解くのは難しいかもしれません。
