トップ› 名古屋大学› 2014年› 理系第4問

名古屋大学 2014年理系第4問解説

方針・初手

与えられた漸化式 $a_{n+1} = \left[\frac{a_n}{2}\right]$ は、ガウス記号の定義に基づいて不等式で評価するのが基本方針です。 (1) は定義式から直接逆算して求めます。 (2) と (3) は、数列の一般項が $a_k = \left[\frac{N}{2^{k-1}}\right]$ と表せることを見抜き、ある項が特定の値になるような $N$ の範囲（区間）を不等式を用いて特定します。各区間が互いに素であることを確認し、条件を満たす区間に含まれる整数の個数を数え上げます。

解法1

(1)

定義 $a_{n+1} = \left[\frac{a_n}{2}\right]$ より、実数 $x$ に対するガウス記号の性質 $[x] \leqq x < [x] + 1$ を用いると、 $$a_{n+1} \leqq \frac{a_n}{2} < a_{n+1} + 1$$ すなわち、 $$2a_{n+1} \leqq a_n < 2a_{n+1} + 2$$ が成り立つ。$a_n$ は整数であるから、$a_n = 2a_{n+1}$ または $a_n = 2a_{n+1} + 1$ となる。 $a_3 = 1$ のとき、 $a_2 = 2 \cdot 1 = 2$ または $a_2 = 2 \cdot 1 + 1 = 3$ である。

・$a_2 = 2$ のとき $a_1 = 2 \cdot 2 = 4$ または $a_1 = 2 \cdot 2 + 1 = 5$

・$a_2 = 3$ のとき $a_1 = 2 \cdot 3 = 6$ または $a_1 = 2 \cdot 3 + 1 = 7$

$a_1 = N$ であるから、求める $N$ は $N = 4, 5, 6, 7$ である。

(2)

任意の正の整数 $k$ に対して、$a_k = \left[\frac{N}{2^{k-1}}\right]$ となることを数学的帰納法で示す。

(i) $k=1$ のとき $a_1 = N = \left[\frac{N}{2^0}\right]$ となり成立する。

(ii) $k=j$ のとき成立すると仮定する。すなわち $a_j = \left[\frac{N}{2^{j-1}}\right]$ とする。ここで、任意の実数 $x$ に対して $\left[\frac{[x]}{2}\right] = \left[\frac{x}{2}\right]$ が成り立つことを示す。 $x = 2p + q + r$ （$p$ は整数、$q \in \{0, 1\}$、$0 \leqq r < 1$）とおく。 $[x] = 2p + q$ であり、$\frac{[x]}{2} = p + \frac{q}{2}$ である。$0 \leqq \frac{q}{2} < 1$ より $\left[\frac{[x]}{2}\right] = p$ となる。一方、$\frac{x}{2} = p + \frac{q+r}{2}$ であり、$0 \leqq \frac{q+r}{2} < \frac{1+1}{2} = 1$ であるから、$\left[\frac{x}{2}\right] = p$ となる。よって $\left[\frac{[x]}{2}\right] = \left[\frac{x}{2}\right]$ が示された。これを用いると、$k=j+1$ のとき、 $$a_{j+1} = \left[\frac{a_j}{2}\right] = \left[\frac{\left[\frac{N}{2^{j-1}}\right]}{2}\right] = \left[\frac{\frac{N}{2^{j-1}}}{2}\right] = \left[\frac{N}{2^j}\right]$$ となり、$k=j+1$ のときも成立する。以上より、すべての正の整数 $k$ に対して $a_k = \left[\frac{N}{2^{k-1}}\right]$ が成り立つ。

数列 $\{a_n\}$ のある項が $2$ となる条件は、ある非負整数 $l$ （$l=k-1$）が存在して $\left[\frac{N}{2^l}\right] = 2$ となることである。これは $2 \leqq \frac{N}{2^l} < 3$、すなわち $$2^{l+1} \leqq N \leqq 3 \cdot 2^l - 1$$ と同値である。この不等式を満たす整数の集合を区間 $I_l = [2^{l+1}, 3 \cdot 2^l - 1]$ とする。 $I_l$ に含まれる整数の個数は $(3 \cdot 2^l - 1) - 2^{l+1} + 1 = 2^l$ 個である。また、$3 \cdot 2^l - 1 < 2 \cdot 2^{l+1} = 2^{l+2}$ より、$I_l$ の最大値は $I_{l+1}$ の最小値よりも小さい。よって各区間 $I_0, I_1, I_2, \cdots$ は互いに素である。

$0 \leqq N < 2^{10}$ の範囲に $I_l$ が含まれる条件を考える。 $2^{l+1} < 2^{10}$ より $l \leqq 8$ である。 $l=8$ のとき、区間は $I_8 = [2^9, 3 \cdot 2^8 - 1] = [512, 767]$ であり、すべての要素は $2^{10} = 1024$ 未満である。よって、条件を満たす $N$ の個数は、$l=0, 1, \cdots, 8$ に対する $I_l$ の要素数の和となる。 $$\sum_{l=0}^{8} 2^l = \frac{2^9 - 1}{2 - 1} = 511$$

(3)

(2) と同様に、ある項が $m$ （$m$ は正の整数）となる条件は、ある非負整数 $l$ が存在して $\left[\frac{N}{2^l}\right] = m$、すなわち $$m \cdot 2^l \leqq N \leqq (m+1) 2^l - 1$$ となることである。この区間を $J_l = [m \cdot 2^l, (m+1) 2^l - 1]$ とする。 $m \geqq 1$ のとき、$(m+1) 2^l \leqq m \cdot 2^{l+1} \iff m+1 \leqq 2m \iff m \geqq 1$ が成り立つため、$J_l$ の最大値は $J_{l+1}$ の最小値以下となり、各 $J_l$ は互いに素である。 $J_l$ に含まれる整数の個数は $2^l$ 個である。

$m$ を 2進法で表したときの桁数を $L$ とおく。すなわち、$2^{L-1} \leqq m \leqq 2^L - 1$ （$L$ は正の整数）とする。 $0 \leqq N < 2^{100}$ の範囲において $J_l$ がどのように含まれるかを調べる。 $l$ を $0 \leqq l \leqq 100 - L$ の範囲で動かすと、 $$(m+1) 2^l \leqq 2^L \cdot 2^{100-L} = 2^{100}$$ となり、$J_l$ に含まれる整数はすべて $2^{100}$ 未満となる。一方、$l = 100 - L + 1$ のとき、$J_l$ の最小値は $$m \cdot 2^{100-L+1} \geqq 2^{L-1} \cdot 2^{100-L+1} = 2^{100}$$ となり、$J_l$ は $0 \leqq N < 2^{100}$ の範囲から完全に外れる。これより大きな $l$ についても同様である。したがって、条件を満たす $N$ の総数 $S(m)$ は $$S(m) = \sum_{l=0}^{100-L} 2^l = \frac{2^{100-L+1} - 1}{2 - 1} = 2^{100-L+1} - 1$$ となる。このとき、条件を満たす確率 $P(m)$ は、全事象が $2^{100}$ 通りであるから、 $$P(m) = \frac{2^{100-L+1} - 1}{2^{100}} = 2^{-L+1} - \frac{1}{2^{100}}$$ となる。条件 ($\ast$) は $P(m) \leqq \frac{1}{100}$ であるから、 $$2^{-L+1} - \frac{1}{2^{100}} \leqq \frac{1}{100}$$ この不等式を満たす $L$ を考える。$\frac{1}{2^{100}} > 0$ であるから、$2^{-L+1} \leqq \frac{1}{100} \iff 2^{L-1} \geqq 100$ であれば十分である。 $2^6 = 64$、$2^7 = 128$ より、$L-1 \geqq 7$ すなわち $L \geqq 8$ のとき十分条件を満たす。一方、$L = 7$ のとき、 $$P(m) = 2^{-6} - \frac{1}{2^{100}} = \frac{1}{64} - \frac{1}{2^{100}}$$ $\frac{1}{64} > \frac{1}{100}$ であり、$\frac{1}{2^{100}}$ は極めて小さな数であるため $\frac{1}{64} - \frac{1}{2^{100}} > \frac{1}{100}$ となり不適である。（$L \leqq 6$ のときはさらに大きくなる）したがって、条件 ($\ast$) を満たすための必要十分条件は $m$ の桁数 $L$ が $L \geqq 8$ を満たすことである。求める最小の正の整数 $m$ は、$L=8$ を満たす最小の正の整数、すなわち $2^{8-1} = 2^7 = 128$ である。

解説

操作 $a_{n+1} = \left[\frac{a_n}{2}\right]$ は、$a_n$ を 2進数表示したときの下1桁を切り捨てる（右に1ビットシフトする）操作と同値です。したがって、「ある項が $m$ になる」ということは、「$N$ の 2進数表示の上位ビット列が $m$ の 2進数表示と完全に一致する」ことと言い換えられます。この観点に立つと、(3) で求めた確率が $m$ の具体的な値によらず、$m$ の「桁数」だけで決まるという結果も直感的に理解しやすくなります。記述式の解答としては、解法1のようにガウス記号の不等式を用いて区間を数え上げる方法が厳密で安全です。