4高知大学 2014年 数学 第4問解答・解説

当たりカードは全 $2^k-1$ 枚の中から一様に1枚選ばれている。初めの組のカード枚数を $2^k-1$ とし、この手順で引く枚数の期待値を $E_k$ とする。

準備 $k\ge2$ とする。最初に中央のカードを1枚引く。当たりがそこにある確率は $1/(2^k-1)$ で、その場合は終了する。外れる確率は $(2^k-2)/(2^k-1)$。外れたとき、当たりを含む側の組は同じ枚数の2組から選ばれ、当たり位置はその組の中で一様である。その組の枚数は $$\displaystyle \frac{(2^k-1)-1}{2}=2^{k-1}-1$$ なので、そこから先の手順の期待引き枚数は $E_{k-1}$ である。最初の1枚を含めると $$\displaystyle E_k=1+\frac{2^k-2}{2^k-1}E_{k-1}\qquad(k\ge2). \tag{1}$$

(1) $k=1$ ではカードは1枚なので $E_1=1$。式(1)を順に使うと $$\displaystyle E_2=1+\frac23E_1=\frac53,\qquad E_3=1+\frac67E_2=\frac{17}{7},\qquad E_4=1+\frac{14}{15}E_3=\frac{49}{15}.$$

(2) 式(1)の $k$ を $k+1$ に置き換えると $$\displaystyle E_{k+1}=1+\frac{2^{k+1}-2}{2^{k+1}-1}E_k =1+\frac{2(2^k-1)}{2^{k+1}-1}E_k\qquad(k\ge1).$$

(3) $m=2^k$ とおく。$d_k$ の定義から $$\displaystyle d_k=E_k-\frac{E_k+1}{m}=\frac{(m-1)E_k-1}{m}. \tag{2}$$ (2)の漸化式を用いて $d_{k+1}$ を整理すると $$\displaystyle \begin{aligned} d_{k+1}&=E_{k+1}-\frac{E_{k+1}+1}{2m}\\ &=\frac{(2m-1)E_{k+1}-1}{2m}\\ &=\frac{(2m-1)+2(m-1)E_k-1}{2m}\\ &=\frac{(m-1)(E_k+1)}{m}=d_k+1, \end{aligned}$$ 最後の等号は(2)から従う。したがって求める漸化式は $$d_{k+1}=d_k+1\qquad(k\ge1).$$

(4) $d_1=E_1-(E_1+1)/2=0$ なので、(3)より $d_k=k-1$。式(2)に代入すると $$\displaystyle \frac{(2^k-1)E_k-1}{2^k}=k-1,$$ よって $$\displaystyle E_k=\frac{(k-1)2^k+1}{2^k-1}.$$

(5) 上の式から $$\displaystyle E_k-k=\frac{k+1-2^k}{2^k-1} =\frac{k/2^k+1/2^k-1}{1-1/2^k}.$$ 問題で与えられた $k/2^k\to0$ と $1/2^k\to0$ を用いると、分子は $-1$ に、分母は $1$ に収束する。従って $$\displaystyle \lim\limits _{k\to\infty}(E_k-k)=-1.$$