🏠 Home / 大学入試 / 京都大学 / 京大理系

京都大学 理系 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$について、次の命題Aが成り立つことを示す。

命題A:$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$ のときに命題Aが成り立つとする。

$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$のときも命題Aが成り立つ。

(1)(2)から、0以上のすべての$n$について、命題Aが成り立つ。

次に、$\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} となる。

【別解終】

とりうる値を出すところまではそんなに難しくないですが、そこから個数を計算するところが激しく難しいです。このやり方だと、時間内に解くのは難しいかもしれません。

関連するページ

YouTubeもやってます