[math][京都大学]2025年京都大学理系数学問題6

Table of Contents

問題

$n$は$2$以上の整数とする。$1$枚の硬貨を続けて$n$回投げる。このとき、$k$回目$(1\leq k\leq n)$に表が出たら$X_k = 1$、裏が出たら$X_k = 0$として、$X_1, X_2, \cdots, X_n$を定める。$$Y_n = \sum_{k = 2}^{n}{X_{k-1}X_k}$$とするとき、$Y_n$が奇数である確率$p_n$を求めよ。

方針

具体的に実験してみる。$n = 2$のとき、$Y_2 = X_1X_2$だから、これが奇数になるのは、$X_1=X_2=1$のときであるから、$\displaystyle p_2 = \frac{1}{4}$である。

$n = 3$のとき、$Y_3 = X_1X_2+X_2X_3$だから、これが奇数になるのは、$(X_1, X_2, X_3) = (1, 1, 0), (0, 1, 1)$のときであるから、$\displaystyle p_3 = \frac{2}{8} = \frac{1}{4}$である。

$n = 4$のとき、$Y_4 = X_1X_2 + X_2X_3 + X_3X_4$だから、これが奇数になるのは
$(i)$ $Y_4 = 3$のとき、$(X_1, X_2, X_3, X_4) = (1, 1, 1, 1)$の$1$通り。
$(ii)$ $Y_4 = 1$のとき、$X_1X_2 = 1$のときは、$(X_1=X_2 = 1)$が必要で、$X_2X_3+X_3X_4=0$だから、$(X_3, X_4) = (0, 0), (0, 1)$の$2$通り。$X_2X_3=1$のときは、$X_2=X_3=1$が必要で、自動的に$X_1=X_4 = 0$となるので$1$通り。$X_3X_4 = 1$のときは$X_1X_2=1$のときと同様に$2$通りだから、合計$5$通り。
以上から、$\displaystyle p_4 = \frac{6}{16} = \frac{3}{8}$となる。

このように見ていくと、漸化式が立てられそうである。補助数列を設定すると良い。

解答

まず、$Y_n$が奇数かつ$X_n=0$となる確率を$q_n$、$Y_n$が奇数かつ$X_n = 1$となる確率を$r_n$とする。$p_n = q_n + r_n$である。また、$Y_n$が偶数かつ$X_n=0$となる確率を$s_n$、$Y_n$が偶数かつ$X_n=1$となる確率を$t_n$とする。$1-p_n = s_n+t_n$である。

$X_{n+1} = 0$となる確率は$\displaystyle \frac{1}{2}$で、このとき、$Y_{n+1} = Y_{n}$であるから、$Y_{n+1}$が奇数になる確率は$Y_n$が奇数になる確率と等しく、$p_{n}$である。したがって、$\displaystyle q_{n+1} = \frac{1}{2}p_n$となる。また、$Y_{n+1}$が偶数になる確率は$Y_n$が偶数になる確率と等しく、$1-p_n$である。したがって、$\displaystyle s_{n+1} = \frac{1}{2}(1-p_n)$となる。

さらに、$X_{n+1} = 1$となる確率は$\displaystyle \frac{1}{2}$で、このとき、$Y_{n+1} = Y_{n} + X_{n}X_{n+1} = Y_n + X_n$であるから、$Y_{n+1}$が奇数になるのは$(i)$ $Y_{n}$が偶数で、$X_{n}=1$のときか、あるいは$(ii)$ $Y_{n}$が奇数で、$X_{n} = 0$のときである。$(i)$の確率は$t_n$で、$(ii)$の確率は$q_n$である。したがって、$\displaystyle r_{n+1}=\frac{1}{2}(t_n+q_n)$となる。また、$Y_{n+1}$が偶数になるのは、$(iii)$ $Y_{n}$が奇数で、$X_n = 1$のときか、あるいは$(iv)$ $Y_n$が偶数で、$X_{n} = 0$のときである。$(iii)$の確率は$r_n$で、$(iv)$の確率は$s_n$である。したがって、$\displaystyle t_{n+1}=\frac{1}{2}(r_n+s_n)$となる。

まとめると、$$\begin{cases}q_{n+1} & = & \displaystyle \frac{1}{2}p_n \\ r_{n+1} & = & \displaystyle \frac{1}{2}(t_n+q_n) \\ s_{n+1} & = & \displaystyle \frac{1}{2}(1-p_n) \\ t_{n+1} & = & \displaystyle \frac{1}{2}(r_n+s_n) \end{cases}$$である。$1, 3$番目の式から$\displaystyle q_{n+1}+s_{n+1} = \frac{1}{2}$、$2, 4$番目の式から$\displaystyle r_{n+1}+t_{n+1} = \frac{1}{2}$である。これを用いると、$$\begin{eqnarray}p_{n+1} & = & q_{n+1} + r_{n+1}\\ & = & \frac{1}{2}p_n + \frac{1}{2}t_n + \frac{1}{2}q_n \\ & = & \frac{1}{2}p_n + \frac{1}{2}\left(\frac{1}{2}-r_n\right) + \frac{1}{2}q_n \\ & = & \frac{1}{2}p_n -\frac{1}{2}r_n+\frac{1}{2}q_n + \frac{1}{4} \\ & = & \frac{1}{2}p_n-\frac{1}{2}(p_n-q_n)+\frac{1}{2}q_n +\frac{1}{4} \\ & = & q_n + \frac{1}{4} \\ & = & \frac{1}{2}p_{n-1}+\frac{1}{4}\end{eqnarray}$$である。書き直すと、$\displaystyle p_{n+2} -\frac{1}{2}= \frac{1}{2}\left(p_n-\frac{1}{2}\right)$となる。$n$を偶奇で分ける。

$n = 2m-1\ (m=2, 3, \cdots)$のとき、$\displaystyle p_{2m+1} -\frac{1}{2} = \frac{1}{2}\left(p_{2m-1}-\frac{1}{2}\right)$である。これを繰り返し使って、$\displaystyle p_{2m-1}-\frac{1}{2}=\left(\frac{1}{2}\right)^{m-2}\left(p_3-\frac{1}{2}\right) = -\frac{1}{4}\left(\frac{1}{2}\right)^{m-2}$となる。$\displaystyle m = \frac{n+1}{2}$であるから、$\displaystyle p_n = \frac{1}{2}-\frac{1}{4}\left(\frac{1}{2}\right)^{\frac{n-3}{2}} = \frac{1}{2}-\left(\frac{1}{2}\right)^{\frac{n+1}{2}}$となる。

$n = 2m\ (m=2, 3, \cdots)$のとき、$\displaystyle p_{2m+2} -\frac{1}{2} = \frac{1}{2}\left(p_{2m}-\frac{1}{2}\right)$である。これを繰り返し使って、$\displaystyle p_{2m}-\frac{1}{2}=\left(\frac{1}{2}\right)^{m-1}\left(p_2-\frac{1}{2}\right) = -\frac{1}{4}\left(\frac{1}{2}\right)^{m-1}$となる。$\displaystyle m = \frac{n}{2}$であるから、$\displaystyle p_n = \frac{1}{2}-\frac{1}{4}\left(\frac{1}{2}\right)^{\frac{n-2}{2}} = \frac{1}{2}-\left(\frac{1}{2}\right)^{\frac{n+2}{2}}$となる。

以上をまとめて、$$p_n = \begin{cases}\displaystyle \frac{1}{2}-\left(\frac{1}{2}\right)^{\frac{n+1}{2}}\ \ (n\equiv 1 \pmod{2})\\ \displaystyle \frac{1}{2}-\left(\frac{1}{2}\right)^{\frac{n+2}{2}}\ (n\equiv 0 \pmod{2})\end{cases}$$となる。

解説

はじめに小さい$n$で様子を確かめることで、どのような方針を立てれば良いのか糸口が掴めるし、答えを出した後の験算にもなる。結果として、$p_n$と$p_{n+2}$の間に関係があることが分かるが、補助数列なしでこれを一気に見抜くのはなかなか難しいと思われる。多少煩わしくなっても、補助数列を設定することで、試験場で手を止めずに記述することができるというメリットがある。