解説

方針・初手

与えられた数列の漸化式 $a_{k+1}(x) = 2a_k(x) - [2a_k(x)]$ は、実数 $y$ に対して $y - [y]$ が $y$ の小数部分を表すことと同義である。この性質から、$a_k(x)$ の一般項を推測し、条件 $(*)$ の意味を明らかにするのが第一歩である。具体的には、$x$ が有限2進小数として表せるかどうかが条件 $(*)$ と結びつく。

解法1

実数 $x$ （$0 < x < 1$）に対して、数列 $\{a_k(x)\}$ の一般項が $a_k(x) = 2^{k-1}x - [2^{k-1}x]$ であることを数学的帰納法で示す。

$k=1$ のとき、与えられた $x$ は $x = \frac{i}{n}$ （$1 \leqq i \leqq n-1$）であるから $0 < x < 1$ であり、$[x] = 0$ となる。 したがって、

$$a_1(x) = x = x - [x] = 2^0x - [2^0x]$$

となり成立する。

$k=m$ のとき、$a_m(x) = 2^{m-1}x - [2^{m-1}x]$ が成立すると仮定する。 漸化式より、

$$a_{m+1}(x) = 2a_m(x) - [2a_m(x)]$$

これに仮定を代入すると、

$$a_{m+1}(x) = 2(2^{m-1}x - [2^{m-1}x]) - [2(2^{m-1}x - [2^{m-1}x])]$$

$$a_{m+1}(x) = 2^mx - 2[2^{m-1}x] - [2^mx - 2[2^{m-1}x]]$$

ここで、任意の整数 $N$ と実数 $y$ について $[y - N] = [y] - N$ が成り立つ性質を利用する。$2[2^{m-1}x]$ は整数であるから、

$$[2^mx - 2[2^{m-1}x]] = [2^mx] - 2[2^{m-1}x]$$

となる。これを上の式に代入すると、

$$a_{m+1}(x) = 2^mx - 2[2^{m-1}x] - ([2^mx] - 2[2^{m-1}x]) = 2^mx - [2^mx]$$

よって、$k=m+1$ のときも成立する。 以上より、すべての正の整数 $k$ について $a_k(x) = 2^{k-1}x - [2^{k-1}x]$ である。

条件 $(*)$ は、ある正の整数 $k$ が存在して $a_k(x) = 0$ となることである。

$$a_k(x) = 0 \iff 2^{k-1}x - [2^{k-1}x] = 0 \iff 2^{k-1}x \text{ が整数}$$

$x = \frac{i}{n}$ であるから、$2^{k-1} \cdot \frac{i}{n}$ が整数となる。

正の整数 $n$ を $n = 2^A \cdot B$ （$A$ は $0$ 以上の整数、$B$ は正の奇数）と素因数分解する。 $2^{k-1} \cdot \frac{i}{n} = \frac{2^{k-1}i}{2^A \cdot B}$ が整数となるためには、$i$ が $B$ の倍数であることが必要十分条件である。 $i = B \cdot j$ （$j$ は整数）とおく。 $i$ は $1 \leqq i \leqq n-1$ を満たすので、

$$1 \leqq B \cdot j \leqq 2^A \cdot B - 1$$

各辺を $B$ で割ると、

$$\frac{1}{B} \leqq j \leqq 2^A - \frac{1}{B}$$

$j$ は整数であるから、$1 \leqq j \leqq 2^A - 1$ となる。 このとき、条件 $(*)$ を満たす有理数 $\frac{i}{n}$ は次のように表される。

$$\frac{i}{n} = \frac{B \cdot j}{2^A \cdot B} = \frac{j}{2^A}$$

**(1)**

$n=12$ のとき、$12 = 2^2 \cdot 3$ であるから、$A=2, B=3$ である。 $j$ の範囲は $1 \leqq j \leqq 2^2 - 1$ より $j = 1, 2, 3$ となる。 したがって、求める有理数は $\frac{j}{2^2} = \frac{j}{4}$ であり、$j=1, 2, 3$ を代入して以下の集合を得る。

$$S_{12} = \left\{ \frac{1}{4}, \frac{2}{4}, \frac{3}{4} \right\} = \left\{ \frac{1}{4}, \frac{1}{2}, \frac{3}{4} \right\}$$

**(2)**

任意の $n$ に対して、$S_n$ の要素は $\frac{j}{2^A}$ （$1 \leqq j \leqq 2^A - 1$）という形で表される。ここで $A$ は $n$ が持つ素因数 $2$ の個数である。 $1 \leqq n \leqq 2018$ の範囲において、$2^A \leqq n$ であるから、

$$2^A \leqq 2018$$

これを満たす最大の整数 $A$ は、$2^{10} = 1024 \leqq 2018 < 2048 = 2^{11}$ より $A = 10$ である。 実際に、$n = 1024$ （すなわち $A=10, B=1$）は $1 \leqq n \leqq 2018$ の範囲に含まれており、このとき

$$S_{1024} = \left\{ \frac{j}{1024} \mathrel{\Bigg|} 1 \leqq j \leqq 1023 \right\}$$

となる。

次に、$1 \leqq n \leqq 2018$ を満たす任意の $n$ について考える。$n = 2^A \cdot B$ とおくと、$A \leqq 10$ である。 $S_n$ の任意の要素 $\frac{j}{2^A}$ （$1 \leqq j \leqq 2^A - 1$）は、分母と分子に $2^{10-A}$ を掛けることで次のように変形できる。

$$\frac{j}{2^A} = \frac{j \cdot 2^{10-A}}{2^{10}} = \frac{j \cdot 2^{10-A}}{1024}$$

ここで、分子は正の整数であり、その最大値は

$$(2^A - 1) \cdot 2^{10-A} = 2^{10} - 2^{10-A} = 1024 - 2^{10-A} \leqq 1023$$

となるため、$j \cdot 2^{10-A}$ は $1$ 以上 $1023$ 以下の整数となる。 したがって、$S_n$ のすべての要素は $S_{1024}$ に含まれることがわかる。 ゆえに、$T = \bigcup_{n=1}^{2018} S_n = S_{1024}$ である。

$T$ の要素の個数は $S_{1024}$ の要素の個数に等しいため、$1023$ 個となる。

解説

与えられた数列 $\{a_k(x)\}$ の漸化式は、実数 $x$ を2進数展開したときの各桁のシフト操作とみなすことができる。ある段階で値が $0$ になるということは、$x$ が「有限2進小数」として表せることを意味している。これに気づけば、$x = \frac{i}{n}$ が有限2進小数となるための条件、すなわち約分した結果の分母が $2$ の冪乗になるという性質へ一本道で帰着できる。 (2)では、$T$ をすべての $S_n$ の和集合として定義しているが、分母の $2$ の冪乗が最大となる $n=1024$ の集合 $S_{1024}$ が他のすべての集合を包含してしまうという構造を見抜くことが鍵である。

答え

(1) $$S_{12} = \left\{ \frac{1}{4}, \frac{1}{2}, \frac{3}{4} \right\}$$

(2) 1023