名古屋大学 2014年度 前期日程 第2次学力試験理系数学 第4問

(1)

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

したがって $a_3=1$ は $$\left[\frac{N}{4}\right]=1$$ と同値である。これは $$1\leqq \frac{N}{4}<2$$ すなわち $4\leqq N<8$ を意味する。$N$ は整数なので $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=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\mathrm{/}100$ 以下となる最小の $m$ を求める。$q=6$ のとき$$\frac{2^{94}-1}{2^{100}}>\frac{2^{94}-2^{87}}{2^{100}}=\frac{127}{8192}>\frac{1}{100}$$である。一方、$q=7$ のとき$$\frac{2^{93}-1}{2^{100}}<\frac{1}{128}<\frac{1}{100}$$である。したがって必要な最小の $q$ は7である。 $q=7$ を満たす最小の正の整数 $m$ は $m=2^7=128$ である。よって求める最小の正の整数は $128$ である。

$[a_n\mathrm{/}2]$ は二進法表示の末尾1桁を消す操作である。この見方で (1) は先頭が1の3桁、(2) は先頭が10の高々10桁、(3) は $m$ の二進法表示を接頭部にもつ整数を数える。

$a_{n+1}=[a_n\mathrm{/}2]$ は、非負整数の二進法表示から末尾の1桁を消す操作である。

(1) $a_3=1$ であるためには、$N$ の二進法表示から末尾2桁を消した結果が $1$ になればよい。したがって$$N=(100{)}_2,(101{)}_2,(110{)}_2,(111{)}_2,$$すなわちである。

(2) ある項が2、すなわち $(10{)}_2$ になるためには、$N$ の二進法表示が $10$ で始まればよい。全体の桁数が $j+2$ 桁なら、その後ろの $j$ 桁は自由なので $2^j$ 個ある。$N<2^{10}$ より $0\leqq j\leqq 8$ だから、個数は$$\sum _{j=0}^8{2}^j=2^9-1=\mathrm{<mn\; mathvariant="bold">511</mn>}$$である。

(3) $2^q\leqq m<2^{q+1}$ とすると、$m$ の二進法表示は $q+1$ 桁である。数列のある項が $m$ になる $N$ は、$m$ の二進法表示の後ろに $j$ 桁を自由につけたものである。$N<2^{100}$ より $0\leqq j\leqq 99-q$ なので、その個数は$$\sum _{j=0}^{99-q}{2}^j=2^{100-q}-1.$$したがって確率は$$\frac{2^{100-q}-1}{2^{100}}\mathrm{.}$$$q=6$ では$$\frac{2^{94}-1}{2^{100}}>\frac{127}{8192}>\frac{1}{100},$$$q=7$ では$$\frac{2^{93}-1}{2^{100}}<\frac{1}{128}<\frac{1}{100}\mathrm{.}$$よって必要な最小の桁区分は $q=7$ であり、その範囲の最小の正整数はである。