4名古屋大学 2014年 数学 第4問解答・解説

まず、整数除算を繰り返すと $$\displaystyle a_n=\left\lfloor\frac{N}{2^{n-1}}\right\rfloor\quad(n\ge1)$$ となる。実際、$N=2^nq+r\quad(0\leq r<2^n)$ と書けば、 $\displaystyle \left\lfloor\frac{N}{2^{n-1}}\right\rfloor=2q+\left\lfloor\frac{r}{2^{n-1}}\right\rfloor$ で、最後の床関数は0または1である。したがってその数を2で整数除算すると $\displaystyle q=\left\lfloor\frac{N}{2^n}\right\rfloor$ となり、漸化式から主張が従う。

(1) $a_3=1$ は $\displaystyle \left\lfloor\frac{N}{4}\right\rfloor=1$ 、すなわち$4\leq N<8$ を意味する。N は整数なので、　 $N=4,5,6,7$.

(2) $k=n-1\geq0$ とおくと、 $$a_{k+1}=2\quad\text{すなわち}\quad 2^{k+1}\leq N<3\cdot2^k.$$ この区間にある整数は$2^k$ 個である。異なるkの区間は、k番目の上端 $3\cdot2^k$ より次の下端 $2^{k+2}$ が大きいため、互いに交わらない。$N<2^{10}$ では $k=0,1,\ldots,8$ だけが可能だから、求める個数は $$\displaystyle \sum\limits _{k=0}^{8}2^k=2^9-1=511.$$

(3) $m\geq1$ を固定する。$a_{k+1}=m$ となる初期値の集合を$B_k$とすると、これは $m2^k\leq N<(m+1)2^k$ を満たす整数N全体である。 隣り合う区間について、次の下端$m2^{k+1}$は前の上端$(m+1)2^k$以上である（$2m\geq m+1$）。よってこれらの区間は重ならない。

まず $1\leq m\leq127$ とする。$k=0,1,\ldots,93$ について、 $(m+1)2^k\leq128\cdot2^{93}=2^{100}$ なので、各 $B_k$ は $0\leq N<2^{100}$ に全て含まれる。従って該当数は少なくとも $$\displaystyle \sum\limits _{k=0}^{93}2^k=2^{94}-1$$ 個であり、確率は $$\displaystyle \frac{2^{94}-1}{2^{100}}=\frac1{64}-\frac1{2^{100}} >\frac1{64}-\frac1{200}=\frac{17}{1600} >\frac1{100}$$ である。ここでは $2^{100}>200$ を用いた。

一方、$m=128$ では $128\cdot2^k<2^{100}$ となるのは $k=0,1,\ldots,92$ だけで、これらの区間はすべて範囲内に全て含まれる。したがって $$\displaystyle \Pr(\text{ある項が }128)=\frac{\sum\limits _{k=0}^{92}2^k}{2^{100}} =\frac{2^{93}-1}{2^{100}} =\frac1{128}-\frac1{2^{100}}<\frac1{128}<\frac1{100}.$$ $1$から$127$までは条件を満たさず、128は満たすので、最小の正整数は　 $m=128$.