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

解答編

問題

 n を自然数とする。投げたとき表裏の出る確率がそれぞれ $\dfrac{1}{2}$ ずつであるような硬貨を用意し、この硬貨を $2^n-1$ 回投げる。このとき、 $2^{n-1}\leqq k\leqq 2^n-1$ である自然数 k のうち少なくとも1つが次の条件(*) を満たす確率を $p_n$ とする。

 (*) n 以下のすべての自然数 m について、 $\left[ \dfrac{k}{2^{n-m}} \right]$ 回目の硬貨投げの結果は表である。

ただし、実数 x に対して、 $[x]$ は x より大きくない最大の整数を表す。

 例えば、 $p_1$ は硬貨を1回投げて表が出る確率を表すので、 $p_1=\dfrac{1}{2}$ である。 $p_2$ は、硬貨を3回投げて、「1回目と2回目がともに表」であるか「1回目と3回目がともに表」であるかの少なくとも一方が成り立つ確率を表すので、 $p_2=\dfrac{3}{8}$ である。
 以下の設問に答えよ。

(1) $p_{n+1}$ を $p_n$ を用いて表せ。

解答

(1)
以下のようにして、数字を並べていく。まず、 $1$ をおき、その右上に $2$ を、右下に $3$ を置く。そして、 $1$ と右上、右下とをそれぞれ線で結ぶ。以降、各自然数 i に対し、右上に $2i$ を、右下に $2i+1$ を置き、線で結んでいき、以下の図のようにする。

自然数 i を2進数表示したとき、一番右の数字に $0$ を追加したものが $2i$ で、 $1$ を追加したものが $2i+1$ であることから、左から n 列目には、上から順番に $2^{n-1}$ から $2^n-1$ の数字が1個ずつ並ぶことがわかる。また、 $\left[ \dfrac{k}{2^{n-m}} \right]$ は、 k を2進数表示したときの、右から $n-m$ 個の数字を取り除いたものになるため、上の並び方では、線をたどって $n-m$ 個左に移動した数字に対応する。

このことから、(*)の条件は、上の図で、「i 回目が表」となる数字 i だけを通って、左端から n 列目まで行ける道が存在することと同値である。

$p_{n+1}$ は、 $n+1$ 列目まで行ける確率である。これは、1回目が表であり、かつ、 $2$ か $3$ を通って $n+1$ 列目まで行ける確率と等しい。 $2$ の道の先にある数字は、2進数で表したときに上から2つ目の位の数字が $0$ である数である。この $0$ を取り除けば、 $1$ から $n$ 列目までの道と構造が同じであることがわかるため、 $2$ を通って $n+1$ 列目まで行ける確率は $p_n$ となる。同様に、 $3$ の道の先にある数字は、2進数で表したときに上から2つ目の位の数字が $1$ であり、これも同じ構造であることから、 $3$ を通って $n+1$ 列目まで行ける確率は $p_n$ となる。

また、このうち、 $2$ を通る道も $3$ を通る道も存在する確率は、 $2$ の道の先と $3$ の道の先にある数字にダブりがないことから、 $p_n^2$ であることがわかる。

以上から
\begin{eqnarray}
p_{n+1}
&=&
\frac{1}{2} \times \left( p_n +p_n -p_n^2 \right) \\[5pt] &=&
p_n-\frac{1}{2}p_n^2 \\[5pt] \end{eqnarray}となることがわかる。

【広告】

問題

(2) $r_n=\dfrac{2}{p_n}-n$ とする。すべての n に対して $r_n\geqq 3$ が成り立つことを示せ。

解答

(2)
(i) $n=1$ のとき
\begin{eqnarray}
r_1
&=&
\frac{2}{p_1}-1 \\[5pt] &=&
4-1 \\[5pt] &\geqq&
3 \\[5pt] \end{eqnarray}となる。

(ii) $n=k$ のとき $r_k\geqq 3$ とすると、 $\dfrac{2}{p_k}\geqq k+3$ が成り立つので
\begin{eqnarray}
r_{k+1}
&=&
\frac{2}{p_{k+1}}-(k+1) \\[5pt] &=&
\frac{2}{p_k-\frac{1}{2}p_k^2}-k-1 \\[5pt] &=&
\frac{4}{p_k(2-p_k)}-k-1 \\[5pt] &=&
\frac{2}{p_k}+\frac{2}{2-p_k}-k-1 \\[5pt] &\geqq &
(k+3)-k-1+\frac{2}{2-p_k} \\[5pt] &\geqq &
2+1+\frac{p_k}{2-p_k} \\[5pt] &\geqq &
3 \\[5pt] \end{eqnarray}なので、 $n=k+1$ のときも $r_{k+1}\geqq 3$ が成り立つ。

(i)(ii)から、すべての自然数 n に対して $r_n\geqq 3$ が成り立つ。

問題

(3) すべての n に対して\[ \frac{2}{n+3+\log n} \leqq p_n \leqq \frac{2}{n+3} \]が成り立つことを示せ。

解答

(3)
(2)より
\begin{eqnarray}
& &
\frac{2}{p_n}-n \geqq 3 \\[5pt] &\iff&
\frac{1}{p_n} \geqq \frac{n+3}{2} \\[5pt] &\iff&
p_n \leqq \frac{2}{n+3} \\[5pt] \end{eqnarray}となるので、右側の不等号は成り立つ。

左側の不等式 $\frac{2}{n+3+\log n} \leqq p_n$ を示す。これは
\begin{eqnarray}
& &
\frac{2}{n+3+\log n} \leqq p_n \\[5pt] &\iff&
n+3+\log n \geqq \frac{2}{p_n} \\[5pt] \end{eqnarray}となるので、最後の不等式を数学的帰納法で示す。

(i) $n=1$ のとき、
\begin{eqnarray}
1+3+\log 1 – \frac{2}{p_1}=4-4=0
\end{eqnarray}より、成り立つ。

(ii) $n=k$ のとき、 $k+3+\log k \geqq \frac{2}{p_k}$ が成り立つとする。 $n=k+1$ のときは
\begin{eqnarray}
& &
(k+1)+3+\log (k+1) -\frac{2}{p_{k+1}} \\[5pt] &=&
k+4+\log (k+1) -\frac{2}{p_k-\frac{1}{2}p_k^2} \\[5pt] &=&
k+4+\log (k+1) -\frac{2}{p_k}-\frac{2}{2-p_k} \\[5pt] \end{eqnarray}ここで、仮定より、
\begin{eqnarray}
& &
k+4+\log (k+1) -\frac{2}{p_k}-\frac{2}{2-p_k} \\[5pt] &\geqq&
k+4+\log (k+1) -(k+3+\log k)-\frac{2}{2-p_k} \\[5pt] &=&
1+\log (k+1) -\log k -1-\frac{p_k}{2-p_k} \\[5pt] &=&
\log (k+1) -\log k-\frac{p_k}{2-p_k} \\[5pt] \end{eqnarray}となる。ここで、
\begin{eqnarray}
\log (k+1) -\log k
&=&
\int_k^{k+1}\frac{1}{x}dx \\[5pt] &\geqq &
\int_k^{k+1}\frac{1}{k+1}dx \\[5pt] &\geqq &
\frac{1}{k+1} \\[5pt] \end{eqnarray}であり、
\begin{eqnarray}
& &
p_n \leqq \frac{2}{n+3} \\[5pt] &\iff&
\frac{2}{p_n} \geqq n+3 \\[5pt] &\iff&
\frac{2}{p_n}-1 \geqq n+2 \\[5pt] &\iff&
-\frac{1}{\frac{2}{p_n}-1} \geqq -\frac{1}{n+2} \\[5pt] &\iff&
-\frac{p_n}{2-p_n} \geqq -\frac{1}{n+2} \\[5pt] \end{eqnarray}が成り立つので、
\begin{eqnarray}
& &
\log (k+1) -\log k-\frac{p_k}{2-p_k} \\[5pt] &\geqq &
\frac{1}{k+1}-\frac{1}{k+2} \\[5pt] &\geqq &
0
\end{eqnarray}が成り立つ。よって、 $n=k+1$ のときも成り立つ。

(i)(ii)より、左側の不等式も成り立つことがわかる。

以上から、すべての自然数 n に対して\[ \frac{2}{n+3+\log n} \leqq p_n \leqq \frac{2}{n+3} \]が成り立つ。

(解答終)

解説

$n=3$ のときは、「1・2・4が表」「1・2・5が表」「1・3・6が表」「1・3・7が表」のどれかが成り立つときです。どの場合も「1が表」ですね。「1が表」という条件を付けると、あとは、「2・4が表」「2・5が表」「3・6が表」「3・7が表」の確率を計算できればいいですね。ここで、前半2つと後半2つにダブりがないこと、前半2つも後半2つも「1・2が表、または、1・3が表」という構造になっていることを利用して考えましょう。(1)の説明は、かなり書きにくいと思います。