名古屋大学 2014年度
理系数学 第4問

解答

(1)

まず、すべての正の整数 $n$ について $a_n=\left[\frac{N}{2^{n-1}}\right]$ であることを確認する。$n=1$ では $a_1=N$ なので成り立つ。$a_n=[N/2^{n-1}]$ とすると

である。よって帰納的に成り立つ。

したがって $a_3=1$ は $\left[\frac{N}{4}\right]=1$ と同値である。これは $1\leqq \frac{N}{4}<2$ すなわち $4\leqq N<8$ を意味する。$N$ は整数なので $\boxed{N=4,5,6,7}$ である。

(2)

ある項が2になるとは、ある整数 $j\geqq 0$ について $\left[\frac{N}{2^j}\right]=2$ となることである。これは $2\leqq \frac{N}{2^j}<3$ すなわち $2^{j+1}\leqq N<3\cdot 2^j$ と同値である。 $0\leqq N<2^{10}$ なので、可能な $j$ は $j=0,1,2,\dots ,8$ である。各 $j$ について、整数 $N$ の個数は $3\cdot 2^j-2^{j+1}=2^j$ 個である。また、これらの区間は互いに重ならない。したがって求める個数は ${\sum }_{j=0}^8{2}^j=2^9-1=\boxed{511}$ である。

(3)

正の整数 $m$ を固定する。ある項が $m$ になる条件は、ある整数 $j\geqq 0$ について $\left[\frac{N}{2^j}\right]=m$ となることである。これは $m{2}^j\leqq N<(m+1)2^j$ である。

ここで $2^q\leqq m<2^{q+1}$ となる整数 $q\geqq 0$ をとる。$0\leqq N<2^{100}$ の範囲で上の条件を満たす $N$ は、$j=0,1,\dots ,99-q$ についてそれぞれ $2^j$ 個ずつある。実際、$j=99-q$ までなら $(m+1)2^j\leqq 2^{q+1}{2}^{99-q}=2^{100}$ であり、$j=100-q$ では $m{2}^j\geqq 2^q{2}^{100-q}=2^{100}$ となって範囲外である。

したがって、ある項が $m$ となる $N$ の個数は ${\sum }_{j=0}^{99-q}{2}^j=2^{100-q}-1$ である。よってその確率は $\frac{2^{100-q}-1}{2^{100}}$ である。

これが $1/100$ 以下となる最小の $m$ を求める。$q=6$ のとき、確率は $\frac{2^{94}-1}{2^{100}}>\frac{2^{93}}{2^{100}}=\frac{1}{128}$ では評価が弱いので、直接 $\frac{2^{94}-1}{2^{100}}>\frac{2^{93}}{2^{100}}=\frac{1}{128}$ だけでは $1/100$ との比較に足りない。より単純に

である。

一方、$q=7$ のとき $\frac{2^{93}-1}{2^{100}}<\frac{1}{2^7}=\frac{1}{128}<\frac{1}{100}$ である。したがって必要な最小の $q$ は7である。 $q=7$ を満たす最小の正の整数 $m$ は $m=2^7=128$ である。よって求める最小の正の整数は $\boxed{128}$ である。

別解。

(3) は2進法で見るとさらに見通しがよい。$a_{n+1}=[a_n/2]$ は、2進法表示で末尾の1桁を消す操作である。したがって、数列のある項が $m$ になるとは、$N$ の2進法表示が、$m$ の2進法表示を先頭部分としてもち、その後ろに何桁かを自由につけた形であることを意味する。 $2^q\leqq m<2^{q+1}$ なら、$m$ の2進法表示は $q+1$ 桁である。$N$ は0以上 $2^{100}-1$ 以下なので、全体の桁数は高々100桁である。後ろにつける自由な桁数は $0,1,2,\dots ,99-q$ であり、個数は $1+2+4+\cdots +2^{99-q}=2^{100-q}-1$ となる。以後は上と同じ比較により、最小の $m$ は $128$ である。