京都大学 2015年度 前期日程 第2次学力試験理系数学 第6問

まず、$x_n$ の取り得る値を調べる。$n=0$ では $$x_0=\frac{1}{2}=\frac{0+\frac{1}{2}}{2^0}$$ である。$n$ 回後に $$x_n=\frac{j+\frac{1}{2}}{2^n}(j=0,1,\dots ,2^n-1)$$ の形の値をそれぞれ等確率で取るとする。このとき $$f_0(x_n)=\frac{x_n}{2}=\frac{j+\frac{1}{2}}{2^{n+1}}$$ であり、$$f_1(x_n)=\frac{x_n+1}{2}=\frac{j+2^n+\frac{1}{2}}{2^{n+1}}$$ である。したがって $n+1$ 回後には $$\frac{k+\frac{1}{2}}{2^{n+1}}(k=0,1,\dots ,2^{n+1}-1)$$ の $2^{n+1}$ 個の値を等確率で取る。よって帰納法により、$n$ 回後の値は $$\frac{j+\frac{1}{2}}{2^n}(j=0,1,\dots ,2^n-1)$$ の $2^n$ 個であり、すべて等確率である。

したがって $x_n<2\mathrm{/}3$ となる確率は、$$\frac{j+\frac{1}{2}}{2^n}<\frac{2}{3}$$ を満たす整数 $j$ の個数を $2^n$ で割ればよい。この不等式は $$j+\frac{1}{2}<\frac{2^{n+1}}{3}$$ である。

$n$ が奇数のとき、$n+1$ は偶数なので $2^{n+1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}3)$ である。よって $$\frac{2^{n+1}}{3}=\frac{2^{n+1}-1}{3}+\frac{1}{3}$$ であり、条件は $$j<\frac{2^{n+1}-1}{3}-\frac{1}{6}$$ となる。したがって条件を満たす $j$ の個数は $\frac{2^{n+1}-1}{3}$ である。

$n$ が偶数のとき、$n+1$ は奇数なので $2^{n+1}\equiv 2(\mathrm{m}\mathrm{o}\mathrm{d}3)$ である。よって $$\frac{2^{n+1}}{3}=\frac{2^{n+1}-2}{3}+\frac{2}{3}$$ であり、条件は $$j<\frac{2^{n+1}-2}{3}+\frac{1}{6}$$ となる。したがって条件を満たす $j$ の個数は $\frac{2^{n+1}+1}{3}$ である。

以上より$$P_n=\{\begin{array}{ll}{\displaystyle \frac{2^{n+1}-1}{3\cdot 2^n}}& (n\text{ が奇数}),\\ {\displaystyle \frac{2^{n+1}+1}{3\cdot 2^n}}& (n\text{ が偶数})\end{array}$$である。これをまとめると $$P_n=\frac{2}{3}+\frac{(-1{)}^n}{3\cdot 2^n}$$ である。

$n$ 回後の値が2進小数の中点 $\{(j+1\mathrm{/}2)\mathrm{/}{2}^n\}$ を等確率で取ることを示す。$2\mathrm{/}3$ 未満の個数 $A_n$ と $1\mathrm{/}3$ 未満の個数 $B_n$ を導入し、左右対称性から$B_n=2^n-A_n$ として、確率の1次漸化式を解く。

まず帰納法により、$n$ 回後の値は$$x_n=\frac{j+\frac{1}{2}}{2^n}(j=0,1,\dots ,2^n-1)$$の $2^n$ 個をそれぞれ確率 $2^{-n}$ で取る。実際、$f_0$ は添字 $j$ をそのまま次の前半へ、$f_1$ は $j+2^n$ として後半へ送るので、帰納法が閉じる。

個数の漸化式から求める方法もある。$n$ 回後の $2^n$ 個の値のうち、$2\mathrm{/}3$ 未満であるものの個数を $A_n$、$1\mathrm{/}3$ 未満であるものの個数を $B_n$ とする。

$n+1$ 回後を作るとき、$f_0(x)=x\mathrm{/}2$ を選んだ場合は、もとの $x$ がどの値でも $$\frac{x}{2}<\frac{1}{2}<\frac{2}{3}$$ となる。したがってこの分だけで $2^n$ 個ある。一方、$f_1(x)=(x+1)\mathrm{/}2$ を選んだ場合は $$\frac{x+1}{2}<\frac{2}{3}$$ すなわち $x<\frac{1}{3}$ であることが必要十分である。よって $A_{n+1}=2^n+B_n$ である。

ここで $n$ 回後の値 $$\frac{j+\frac{1}{2}}{2^n}(j=0,1,\dots ,2^n-1)$$ は、$x$ が現れれば $1-x$ も現れるという左右対称な並びである。また $1\mathrm{/}3,2\mathrm{/}3$ と一致する値はない。したがって $1\mathrm{/}3$ 未満の個数は $2\mathrm{/}3$ より大きい個数に等しく、$B_n=2^n-A_n$ である。ゆえに $$A_{n+1}=2^n+(2^n-A_n)=2^{n+1}-A_n$$ を得る。

$P_n=A_n\mathrm{/}{2}^n$ とおくと $$P_{n+1}=1-\frac{P_n}{2}$$ である。初期値は $P_0=1$ であり、$$P_{n+1}-\frac{2}{3}=-\frac{1}{2}(P_n-\frac{2}{3})$$ だから$$P_n-\frac{2}{3}={(-\frac{1}{2})}^n(1-\frac{2}{3})=\frac{(-1{)}^n}{3\cdot 2^n}$$である。したがって $$P_n=\frac{2}{3}+\frac{(-1{)}^n}{3\cdot 2^n}$$ となる。