トップ› 大阪大学› 2016年› 理系第4問

大阪大学 2016年理系第4問解説

方針・初手

(1)は、調和級数（分数の和）の各項に $2^N A_n$ を掛けたときに、分母の素因数2がどのように約分されるかに着目する。

(2)は、(1)の結論を用いて分母の素因数2の個数を評価し、$n$ のとりうる範囲を絞り込んでから具体的に探す。

(3)は、$A_{20} S_{20}$ の小数部分を求める問題である。そのまま分数の足し算をするのではなく、和の分母が最大となる2の冪乗（ここでは $2^4=16$ ）を全体に掛けて、合同式を用いて処理するアプローチが有効である。

解法1

(1)

$N$ は $\log_2 n$ 以下の最大の整数であるから、$N \leqq \log_2 n < N+1$ より、以下が成り立つ。

$$ 2^N \leqq n < 2^{N+1} $$

$1$ 以上 $n$ 以下の任意の整数 $k$ は、非負整数 $j$ と奇数 $c$ を用いて $k = 2^j c$ と表すことができる。

$k \leqq n < 2^{N+1}$ であるから、$2^j \leqq 2^j c < 2^{N+1}$ となり、$j \leqq N$ である。

ここで、$j=N$ となる $k$ は $k=2^N$ のみであることを示す。もし $j=N$ となる別の $k$ が存在するとすれば、$c$ は $3$ 以上の奇数となるため、以下のようになる。

$$ k \geqq 2^N \cdot 3 = 2^{N+1} + 2^N > 2^{N+1} $$

これは $k < 2^{N+1}$ に矛盾する。したがって、$j=N$ となるのは $k=2^N$ のみであり、$k \neq 2^N$ である他のすべての整数については $j \leqq N-1$ となる。

問題の式を展開する。

$$ 2^N A_n S_n = \sum_{k=1}^n \frac{2^N A_n}{k} $$

和の各項 $T_k = \frac{2^N A_n}{k}$ について考える。

$k = 2^N$ のとき、

$$ T_{2^N} = \frac{2^N A_n}{2^N} = A_n $$

$A_n$ は奇数の積であるため、$T_{2^N}$ は奇数である。

$k \neq 2^N$ のとき、$k = 2^j c$ ($j \leqq N-1$) であるから、

$$ T_k = \frac{2^N A_n}{2^j c} = 2^{N-j} \frac{A_n}{c} $$

$c$ は $1$ 以上 $n$ 以下の奇数であるから、$A_n$ の約数であり、$\frac{A_n}{c}$ は整数となる。また、$N-j \geqq 1$ であるから、$T_k$ は偶数の整数である。

よって、全体の和は以下のように表せる。

$$ 2^N A_n S_n = T_{2^N} + \sum_{k \neq 2^N} T_k = (\text{奇数}) + (\text{偶数の和}) $$

したがって、$2^N A_n S_n$ は奇数の整数である。

(2)

(1)より、$2^N A_n S_n$ は奇数の整数であるから、これを奇数 $K$ とおく。

$$ S_n = \frac{K}{2^N A_n} $$

一方で、条件より以下が成り立つ。

$$ S_n = 2 + \frac{m}{20} = \frac{m+40}{20} = \frac{m+40}{2^2 \cdot 5} $$

これら2つの式から $S_n$ を消去して整理する。

$$ \frac{K}{2^N A_n} = \frac{m+40}{2^2 \cdot 5} $$

$$ 2^2 \cdot 5 K = 2^N A_n (m+40) $$

$K$ と $A_n$ は奇数である。また、$m$ は正の整数であるため、両辺はともに正の整数となる。両辺に含まれる素因数 $2$ の個数に着目する。左辺は $2^2 \cdot (\text{奇数})$ であるため、素因数 $2$ をちょうど $2$ 個持つ。右辺の素因数 $2$ の個数は $N$ 個以上である。したがって、両辺が等しくなるためには、少なくとも $N \leqq 2$ でなければならない。

$N = \lfloor \log_2 n \rfloor \leqq 2$ より、$n < 2^3 = 8$ となり、$n$ は $1 \leqq n \leqq 7$ の範囲に限られる。各 $n$ について調べる。

(i)

$n=1$ のとき $S_1 = 1$ より $2 + \frac{m}{20} = 1$、$m = -20$ となり不適。

(ii)

$n=2$ のとき $S_2 = \frac{3}{2}$ より $2 + \frac{m}{20} = \frac{3}{2}$、$m = -10$ となり不適。

(iii)

$n=3$ のとき $S_3 = \frac{11}{6}$ より $2 + \frac{m}{20} = \frac{11}{6}$、$m = -\frac{10}{3}$ となり不適。

(iv)

$n=4$ のとき $S_4 = \frac{25}{12}$ より $2 + \frac{m}{20} = \frac{25}{12}$、$m = \frac{5}{3}$ となり不適。

(v)

$n=5$ のとき $S_5 = \frac{137}{60}$ より $2 + \frac{m}{20} = \frac{137}{60}$、$m = \frac{17}{3}$ となり不適。

(vi)

$n=6$ のとき $S_6 = \frac{137}{60} + \frac{1}{6} = \frac{49}{20}$ より $2 + \frac{m}{20} = \frac{49}{20}$。よって $m = 9$ となり、適する。

(vii)

$n=7$ のとき $S_7 = \frac{49}{20} + \frac{1}{7} = \frac{363}{140}$ より $2 + \frac{m}{20} = \frac{363}{140}$、$m = \frac{83}{7}$ となり不適。

以上より、条件を満たす組は $(n, m) = (6, 9)$ のみである。

(3)

$A_{20} S_{20} = a + b$ において、$a$ は整数、$0 \leqq b < 1$ であるから、$b$ は $A_{20} S_{20}$ の小数部分に等しい。

$$ A_{20} S_{20} = \sum_{k=1}^{20} \frac{A_{20}}{k} $$

$20$ 以下の整数 $k$ のうち、素因数 $2$ を最も多く持つのは $k=16=2^4$ であるため、全体の分母を払うために $16$ を掛ける。

$$ 16 A_{20} S_{20} = \sum_{k=1}^{20} \frac{16 A_{20}}{k} $$

各 $k$ を $k=2^j c$ （$c$ は奇数）と表すと、各項は $\frac{16 A_{20}}{2^j c} = 2^{4-j} \frac{A_{20}}{c}$ となる。これが法 $16$ においてどの値に合同になるかを $j$ ごとに分類して計算する。

(i)

$j=0$ のとき（$k=1,3,5,\dots,19$） $2^4 \frac{A_{20}}{c} = 16 \frac{A_{20}}{c} \equiv 0 \pmod{16}$。

(ii)

$j=1$ のとき（$k=2,6,10,14,18$） $k=2c$ より $c=1,3,5,7,9$ の $5$ 個。各項は $2^3 \frac{A_{20}}{c} = 8 \frac{A_{20}}{c}$ となる。$\frac{A_{20}}{c}$ は奇数であるから、$8 \times (\text{奇数}) \equiv 8 \pmod{16}$。項は $5$ 個あるので、和は $8 \times 5 = 40 \equiv 8 \pmod{16}$。

(iii)

$j=2$ のとき（$k=4,12,20$） $k=4c$ より $c=1,3,5$ の $3$ 個。各項は $4 \frac{A_{20}}{c}$ となる。まず、$A_{20} \pmod 4$ を計算する。

$$ A_{20} = 1 \cdot 3 \cdot 5 \cdot 7 \cdot 9 \cdot 11 \cdot 13 \cdot 15 \cdot 17 \cdot 19 $$

法 $4$ において、$1, 5, 9, 13, 17 \equiv 1 \pmod 4$ であり、$3, 7, 11, 15, 19 \equiv 3 \equiv -1 \pmod 4$ であるから、

$$ A_{20} \equiv 1^5 \cdot (-1)^5 = -1 \equiv 3 \pmod 4 $$

これを用いて各 $\frac{A_{20}}{c} \pmod 4$ を求める。 $c=1$ のとき、$\frac{A_{20}}{1} \equiv 3 \pmod 4$ より $4 \frac{A_{20}}{1} \equiv 12 \pmod{16}$ $c=3$ のとき、$3 \frac{A_{20}}{3} \equiv 3 \pmod 4$ より $\frac{A_{20}}{3} \equiv 1 \pmod 4$。よって $4 \frac{A_{20}}{3} \equiv 4 \pmod{16}$ $c=5 \equiv 1$ のとき、$\frac{A_{20}}{5} \equiv 3 \pmod 4$ より $4 \frac{A_{20}}{5} \equiv 12 \pmod{16}$ これらの和は $12 + 4 + 12 = 28 \equiv 12 \pmod{16}$。

(iv)

$j=3$ のとき（$k=8$） $c=1$ より、項は $2 A_{20}$ となる。$A_{20} \pmod 8$ を計算する。

$$ 1 \cdot 3 \cdot 5 \cdot 7 = 105 \equiv 1 \pmod 8 $$

$$ 9 \cdot 11 \cdot 13 \cdot 15 \equiv 1 \cdot 3 \cdot 5 \cdot 7 \equiv 1 \pmod 8 $$

$$ 17 \cdot 19 \equiv 1 \cdot 3 = 3 \pmod 8 $$

よって、$A_{20} \equiv 1 \cdot 1 \cdot 3 = 3 \pmod 8$ である。 $A_{20} = 8M + 3$ （$M$ は整数）とおけるので、$2 A_{20} = 16M + 6 \equiv 6 \pmod{16}$。

(v)

$j=4$ のとき（$k=16$） $c=1$ より、項は $A_{20}$ となる。$A_{20} \pmod{16}$ を計算する。

$$ 1 \cdot 3 \cdot 5 \cdot 7 = 105 \equiv 9 \pmod{16} $$

$$ 9 \cdot 11 \cdot 13 \cdot 15 \equiv 9 \cdot (-5) \cdot (-3) \cdot (-1) = -135 \equiv 9 \pmod{16} $$

$$ 17 \cdot 19 \equiv 1 \cdot 3 = 3 \pmod{16} $$

よって、$A_{20} \equiv 9 \cdot 9 \cdot 3 = 243 \equiv 3 \pmod{16}$。

以上の（i）から（v）を足し合わせると、

$$ 16 A_{20} S_{20} \equiv 0 + 8 + 12 + 6 + 3 = 29 \equiv 13 \pmod{16} $$

これは、$16 A_{20} S_{20}$ が整数であり、$16 A_{20} S_{20} = 16K + 13$ （$K$ は整数）と表せることを意味する。両辺を $16$ で割ると、

$$ A_{20} S_{20} = K + \frac{13}{16} $$

$K$ は整数であり、$0 \leqq \frac{13}{16} < 1$ を満たすので、$b = \frac{13}{16}$ となる。

解説

本問は、調和級数に関連する整数問題の典型的なテーマである。分数和を整数に変換する際、分母に含まれる素因数2の最大冪に着目する手法は入試数学で頻出である。 (1)で $2^N$ 以外の項の分母が $2^{N-1}$ 以下の2の冪しか持たないことを示し、全体が奇数になることを証明する流れは基本手技として押さえておきたい。 (3)では、すべての項を直接通分して計算することは現実的ではない。全体の分母となる16を掛けたうえで、$\bmod{16}$ の合同式を用いると、計算量を大幅に削減できる。各項が持つ2の冪乗に応じて、適切に法を選んで合同式を立てる処理がカギとなる。