京都大学理学部特色入試 2025年度第2問解説

🕒 2024/11/17 🔄 2024/11/18

（2024年11月に行われた特色入試の問題です。）

問題編

問題

　$n$ を $5$ 以上の自然数とする。 $\mathrm{K}, \mathrm{O}, \mathrm{T}, \mathrm{Y}$ が1文字ずつ書かれた4枚のカード\[ \boxed{ \mathrm{K} },\ \boxed{ \mathrm{O} },\ \boxed{ \mathrm{T} },\ \boxed{ \mathrm{Y} } \]を用意する。この4枚のカードから1枚を引き、書かれた文字を記録し、戻すという操作を $n$ 回繰り返し、記録された順に文字を左から並べる。

　このとき、並んだ $n$ 個の文字の中に連続した文字列「$\mathrm{KYOTO}$」が現れる確率 $p_n$ が\[ p_n\geqq 1-\left(\frac{1023}{1024}\right)^{n-4} \]を満たすことを示せ。

　ただし、上の操作においては、それぞれのカードを毎回独立に、等しい確率で引くものとする。

考え方

KYOTO を含む確率、と言っていますが、何個含むかはわからず、考えにくいので、（よくある手法ですが）含まない確率を考えます。ただ、含まないケースもなかなか考えづらいです。

$n$ 文字のケースと $n+1$ 文字のケースを比較して、どういう違いが出てくるかを考えます。

解答編

問題

　$n$ を $5$ 以上の自然数とする。 $\mathrm{K}, \mathrm{O}, \mathrm{T}, \mathrm{Y}$ が1文字ずつ書かれた4枚のカード\[ \boxed{ \mathrm{K} },\ \boxed{ \mathrm{O} },\ \boxed{ \mathrm{T} },\ \boxed{ \mathrm{Y} } \]を用意する。この4枚のカードから1枚を引き、書かれた文字を記録し、戻すという操作を $n$ 回繰り返し、記録された順に文字を左から並べる。

　このとき、並んだ $n$ 個の文字の中に連続した文字列「$\mathrm{KYOTO}$」が現れる確率 $p_n$ が\[ p_n\geqq 1-\left(\frac{1023}{1024}\right)^{n-4} \]を満たすことを示せ。

　ただし、上の操作においては、それぞれのカードを毎回独立に、等しい確率で引くものとする。

解答

$q_n=1-p_n$ とする。これは、長さ $n$ の文字の中に $\mathrm{KYOTO}$ が含まれない確率である。

また、長さ $n$ の文字の中に $\mathrm{KYOTO}$ が含まれず、かつ、最後の4文字が $\mathrm{KYOT}$ である確率を $a_n$ とおく。

$q_n-q_{n+1}$ は、長さ $n+1$ の文字の中で、はじめの $n$ 文字には $\mathrm{KYOTO}$ が含まれないが、 $n+1$ 文字目まで見ると $\mathrm{KYOTO}$ が含まれる確率である。つまり、 $n+1$ 文字の最後が $\mathrm{KYOTO}$ で終わっており、他に $\mathrm{KYOTO}$ を含まない確率なので、\[ q_n-q_{n+1}=\frac{1}{4}a_n \]が成り立つ。特に、 $q_n\geqq q_{n+1}$ もわかる。つまり、 $\{q_n\}$ は単調減少である。

$a_n$ は、 $\mathrm{KYOTO}$ を含まない $n-4$ 文字のあとに $\mathrm{KYOT}$ が続く確率なので\[ a_n=\frac{1}{4^4}q_{n-4} \]が成り立つ。

これらから
\begin{eqnarray} q_n-q_{n+1} &=& \frac{1}{4}a_n \\[5pt] &=& \frac{1}{4^5}q_{n-4} \\[5pt] &\geqq& \frac{1}{1024}q_n \\[5pt] \end{eqnarray}となるので、\[ \frac{1023}{1024}q_n \geqq q_{n+1} \]が成り立つ。 \begin{eqnarray} q_n & \leqq & \frac{1023}{1024}q_{n-1} \\[5pt] & \leqq & \left(\frac{1023}{1024}\right)^2 q_{n-2} \\[5pt] & \leqq & \left(\frac{1023}{1024}\right)^{n-5} q_5 \\[5pt] & = & \left(\frac{1023}{1024}\right)^{n-5} \cdot\frac{1023}{1024} \\[5pt] & = & \left(\frac{1023}{1024}\right)^{n-4} \end{eqnarray}となるので \begin{eqnarray} p_n=1-q_n\geqq 1-\left(\frac{1023}{1024}\right)^{n-4} \end{eqnarray}が成り立つ。（終）