[math][京都大学][特色入試]2025年京都大学理学部特色入試第2問

math

2025.01.25

Table of Contents

問題

$n$を$5$以上の自然数とする。$\text{K, O, T, Y}$が$1$文字ずつ書かれた$4$枚のカード$$\fbox{K}, \fbox{O}, \fbox{T}, \fbox{Y}$$を用意する。この$4$枚のカードから$1$枚を引き、書かれた文字を記録し、戻すという操作を$n$回繰り返し、記録された順に文字を左から並べる。
このとき、並んだ$n$個の文字の中に連続した文字列「$\text{KYOTO}$」が現れる確率$p_n$が$$p_n\geq 1-\left(\frac{1023}{1024}\right)^{n-4}$$を満たすことを示せ。
　ただし、上の操作においては、それぞれのカードを毎回独立に、等しい確率で引くものとする。

方針

漸化式を立ててみる。

解答

$n$回の施行後、$\text{KYOTO}$の文字が揃っている場合、$n+1$回目は何が出ても$\text{KYOTO}$が揃っている。また、$n$回まで$\text{KYOTO}$の文字が揃っておらず、$n+1$回目で初めて揃う場合を考えると、$n-4$回目までは揃っておらず、$n-3$回目で$\text{K}$、$n-2$回目で$\text{Y}$、$n-1$回目で$\text{O}$、$n$回目で$\text{T}$、$n+1$回目で$\text{O}$が出れば良いので、$$p_{n+1} = p_{n} + (1-p_{n-4})\times \left(\frac{1}{4}\right)^{5}$$となる。$0\leq p_n\leq 1$であるから、$p_n$が単調増加数列であることがここからわかる。変形すると、$$1024p_{n+1} = 1024p_{n} -p_{n-4} + 1$$となる。

$p_{n-4}\leq p_{n}$であるから、$$1024p_{n+1} \geq 1024p_n – p_n + 1 $$である。整理すると、$1024p_{n+1}\geq 1023p_{n} + 1$である。これを用いて数学的帰納法で題意を示す。$\displaystyle p_5 = \frac{1}{4^5} = \frac{1}{1024}$であるから、$n = 5$のとき$\displaystyle p_n\geq 1-\left(\frac{1023}{1024}\right)^{n-4}$が成り立つ。$n = k$で$\displaystyle p_k\geq 1-\left(\frac{1023}{1024}\right)^{k-4}$が成り立つと仮定すると、$$\begin{eqnarray}p_{k+1} & \geq & \frac{1023p_{k} + 1}{1024} \\ & = & \frac{1023}{1024}\left(1-\left(\frac{1023}{1024}\right)^{k-4}\right) + \frac{1}{1024} \\ & = & 1- \left(\frac{1023}{1024}\right)^{k-3}\end{eqnarray}$$となり、$n = k+1$に於いても題意が成り立つ。したがって、すべての$n$に於いて与えられた不等式が成立する。

解説

$p_n$の特性方程式$1024t^5=1024t^4-t+1$の解は$\displaystyle t = 1, \frac{\pm 1 \pm i}{8}$となる。これから$p_n$を求めることもできなくはないが、問題を解く上であまり役には立たない。漸化式を立てたり、問題を考察する過程で$p_n$が単調増加数列であることはすぐに分かる。これを用いると、問題解決に近づくことができるだろう。