正の整数$n$に対して
\[ S_n=\sum_{k=1}^n\frac{1}{k}\]
とおき，$1$以上$n$以下のすべての奇数の積を$A_n$とする．
(1) $\log _2n$以下の最大の整数を$N$とするとき，$2^NA_nS_n$は奇数の整数であることを示せ．
(2) $S_n=2+\dfrac{m}{20}$となる正の整数の組$(n,m)$をすべて求めよ．
(3) 整数$a$と$0\leqq b<1$を満たす実数$b$を用いて
\[ A_{20}S_{20}=a+b\]
と表すとき，$b$の値を求めよ．
(2016年度 大阪大学 前期 理系 第4問)
当記事で紹介する解答は大阪大学が示した解答ではありません．
まずは実験して問題内容を理解するところから始めよう．
(1)は奇数であることの証明であるから，素因数$2$に注目し，(2)や(3)の誘導になっていないかを確認しよう．
(2)は整数問題の解法｢不等式で範囲を絞り込む｣が使えそうである．
(3)は$A_{20}S_{20}$の小数部分を求める問題である．式変形で整数の形を作り出して排除していき，小数部分を決定しよう．
まずは(1)から．とりあえず実験してみよう．
$n=1$のとき
\[ S_1=1\]
\[ A_1=1\]
であり，$\log _21=0$より$N=0$であるから
\[ 2^NA_nS_n=2^0\cdot 1\cdot 1=1\]
したがって，$2^NA_nS_n$は奇数である．
$n=2$のとき
\[ S_2=1+\frac{1}{2}=\frac{3}{2}\]
\[ A_2=1\]
であり，$\log _22=1$より$N=1$であるから
\[ 2^NA_nS_n=2^1\cdot 1\cdot \frac{3}{2}=3\]
したがって，$2^NA_nS_n$は奇数である．
$n=3$のとき
\[ S_3=1+\frac{1}{2}+\frac{1}{3}=\frac{11}{6}\]
\[ A_3=1\cdot 3=3\]
であり，$1<\log _23<2$より$N=1$であるから
\[ 2^NA_nS_n=2^1\cdot 3\cdot \frac{11}{6}=11\]
したがって，$2^NA_nS_n$は奇数である．
$n=4$のとき
\[ S_4=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}=\frac{25}{12}\]
\[ A_4=1\cdot 3=3\]
であり，$\log _24=2$より$N=2$であるから
\[ 2^NA_nS_n=2^2\cdot 3\cdot \frac{25}{12}=25\]
したがって，$2^NA_nS_n$は奇数である．
$n=5$のとき
\[ S_5=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}=\frac{137}{60}\]
\[ A_5=1\cdot 3\cdot 5=15\]
であり，$2<\log _25<3$より$N=2$であるから
\[ 2^NA_nS_n=2^2\cdot 15\cdot \frac{137}{60}=137\]
したがって，$2^NA_nS_n$は奇数である．
さて，実験の結果から，たしかに$2^NA_nS_n$は奇数であることが分かる．
とりあえず，(1)で示すべきことの主張｢$2^NA_nS_n$は奇数｣は真であるから，この証明を考えよう．
$S_n$を$n$の閉じた式で表すことは容易ではないから，$\sum$の中身に注目しよう．
また，奇数であることの証明であるから，素因数$2$に注目するのは自然なことである．
$1$以上$n$以下の整数$k$が持つ素因数$2$の個数を$N_k$とおくと，奇数$p_k$を用いて$k=2^{N_k}p_k$と表すことができる．このとき
\[ 2^NA_nS_n=2^NA_n\sum_{k=1}^n\frac{1}{k}=\sum_{k=1}^n2^{N-N_k}\cdot \frac{A_n}{p_k}\]
さて，$p_k$は$k$以下の奇数，すなわち$n$以下の奇数であるから，明らかに$A_n$の約数である．よって，$\dfrac{A_n}{p_k}$は整数，特に奇数である．
ここで，$N$について考えてみよう．$N$は
\[ N\leqq \log _2n<N+1\]
すなわち
\[ 2^N\leqq n<2^{N+1}\tag{A}\]
を満たす．よって，$2^N$は$1$以上$n$以下の整数のうち，素因数$2$を最も多く持つ整数である．また，素因数$2$を$N$個持つ正の整数は，小さい順に$2^N,2\cdot 2^N,3\cdot 2^N,\dots $であるが
\[ n<2^{N+1}=2\cdot 2^N\]
より，$2^N$は$1$以上$n$以下の整数のうち，素因数$2$を$N$個持つ唯一の数であることが分かる．すなわち，$N_k=N$となるのは$k=2^N$のときのみである．
したがって，$k=2^N$のとき$2^{N-N_k}=1$で奇数であり，$k\neq 2^N$のとき$2^{N-N_k}>1$は偶数であるから，$2^NA_nS_n$は$1$個の奇数と$n-1$個の偶数の和で表すことができる．よって，$2^NA_nS_n$は奇数である．
次に，(2)について考えてみよう．初見では$S_n>2$で$n$の範囲が絞り込めそうだが，おそらく(1)が誘導になっているはずなので，$2^NA_nS_n$を考えてみよう．
\[ 2^NA_nS_n=2^NA_n\left( 2+\frac{m}{20}\right) =2^{N+1}A_n+2^{N-2}\cdot \frac{mA_n}{5}\]
(1)で$2^NA_nS_n$が奇数であることを示したので，それを用いると，$2^{N+1}A_n$は偶数であるから$2^{N-2}\cdot \dfrac{mA_n}{5}$は奇数である．
よって，$N\leqq 2$であるから，$\rm (A)$より
\[ n<2^{N+1}\leqq 2^{2+1}=8\]
なんと$n$の範囲を絞り込むことに成功した．そういえば$S_n>2$でも$n$の範囲が絞り込めそうだった．最初の実験結果を参考にすると
\[ S_3=\frac{11}{6}<2<\frac{25}{12}=S_4\]
より$n>3$であることが分かる．以上より
\[ 4\leqq n\leqq 7\]
かなり絞り込めた．あとはしらみつぶしに確かめよう．
\[ S_4=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}=\frac{25}{12}\]
\[ S_5=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}=\frac{137}{60}\]
\[ S_6=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}=\frac{147}{60}=2+\frac{9}{20}\tag{B}\]
\[ S_7=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}=\frac{1089}{420}=2+\frac{83}{140}\]
よって，$\rm (B)$が条件を満たしているから，$(n,m)=(6,9)$が解である．
最後は(3)である．時間と根気さえあれば手を動かすだけで答えが出る問題ではあるが，それでは面白くないし，時間もかかる．要するに$A_{20}S_{20}$の小数部分を求める問題である．
\[ A_{20}S_{20}=A_{20}\sum_{k=1}^{20}\frac{1}{k}=\sum_{k=1}^{20}\frac{A_{20}}{k}\]
この後どうするか．とりあえず$A_{20}$は$1$以上$20$以下のすべての奇数の積であるから，$k$が奇数のときと偶数のときとで分けよう．
\[ A_{20}S_{20}=\sum_{k=1}^{10}\left( \frac{A_{20}}{2k-1}+\frac{A_{20}}{2k}\right) =\sum_{k=1}^{10}\frac{A_{20}}{2k-1}+\sum_{k=1}^{10}\frac{A_{20}}{2k}\]
$1$以上$10$以下の整数$k$について，$\frac{A_{20}}{2k-1}$は整数であるから，$\displaystyle \sum_{k=1}^{10}\frac{A_{20}}{2k-1}$は整数．今回注目したいのは小数部分であるから，$\displaystyle \sum_{k=1}^{10}\frac{A_{20}}{2k}$について考えればよい．
\[ \begin{aligned}\sum_{k=1}^{10}\frac{A_{20}}{2k}&=\frac{A_{20}}{2}\sum_{k=1}^{10}\frac{1}{k}\\ &=\frac{A_{20}}{2}\left( S_7+\frac{1}{8}+\frac{1}{9}+\frac{1}{10}\right) \\ &=\frac{A_{20}}{2}\left( 2+\frac{83}{140}+\frac{121}{360}\right) \\ &=A_{20}\left( 1+\frac{2341}{2^4\cdot 3^2\cdot 5\cdot 7}\right) \\ &=A_{20}+\frac{1}{16}\cdot \frac{2341A_{20}}{3^2\cdot 5\cdot 7}\end{aligned}\]
$A_20$は整数であるから
\[ \frac{1}{16}\cdot \frac{2341A_{20}}{3^2\cdot 5\cdot 7}\]
の小数部分を考えればよい．特に，$\dfrac{2341A_{20}}{3^2\cdot 5\cdot 7}$は整数であるから，$\dfrac{2341A_{20}}{3^2\cdot 5\cdot 7}$を$16$で割ったときの余りを$c$とすると，$b=\dfrac{c}{16}$になるはずである．
となると，$16$を法とする合同式で処理できそうだ．
\[ \begin{aligned}\dfrac{2341A_{20}}{3^2\cdot 5\cdot 7}&=2341\cdot 3\cdot 11\cdot 13\cdot 15\cdot 17\cdot 19\\ &\equiv 5\cdot 3\cdot (-5)\cdot (-3)\cdot (-1)\cdot 1\cdot 3\\ &=15\cdot 15\cdot (-1)\cdot 3\equiv (-1)\cdot (-1)\cdot (-3)\\ &=-3\equiv 13\pmod{16}\end{aligned}\]
よって，$b=\dfrac{13}{16}$である．
以上の議論をまとめると次のようになる．
(1)難易度:★★★☆☆
$1$以上$n$以下の整数$k$が持つ素因数$2$の個数を$N_k$とおくと，奇数$p_k$を用いて$k=2^{N_k}p_k$と表すことができる．このとき
\[ 2^NA_nS_n=2^NA_n\sum_{k=1}^n\frac{1}{k}=\sum_{k=1}^n2^{N-N_k}\cdot \frac{A_n}{p_k}\]
$p_k$は$k$以下の奇数，すなわち$n$以下の奇数であるから，$A_n$の約数である．よって，$\dfrac{A_n}{p_k}$は整数，特に奇数である．
ここで，$N$は
\[ N\leqq \log _2n<N+1\]
すなわち
\[ 2^N\leqq n<2^{N+1}\tag{A}\]
を満たすから，$2^N$は$1$以上$n$以下の整数のうち，素因数$2$を最も多く持つ整数である．また，素因数$2$を$N$個持つ正の整数は，小さい順に$2^N,2\cdot 2^N,3\cdot 2^N,\dots $であるが
\[ n<2^{N+1}=2\cdot 2^N\]
より，$2^N$は$1$以上$n$以下の整数のうち，素因数$2$を$N$個持つ唯一の数である．すなわち，$N_k=N$となるのは$k=2^N$のときのみである．
したがって，$k=2^N$のとき$2^{N-N_k}=1$で奇数であり，$k\neq 2^N$のとき$2^{N-N_k}$は偶数であるから，$2^NA_nS_n$は$1$個の奇数と$n-1$個の偶数の和で表すことができる．よって，$2^NA_nS_n$は奇数である．$\blacksquare$
(2)難易度:★★★☆☆
\[ 2^NA_nS_n=2^NA_n\left( 2+\frac{m}{20}\right) =2^{N+1}A_n+2^{N-2}\cdot \frac{mA_n}{5}\]
(1)より，$2^{N+1}A_n$は偶数であるから$2^{N-2}\cdot \dfrac{mA_n}{5}$は奇数である．
よって，$N\leqq 2$であるから，$\rm (A)$より
\[ n<2^{N+1}\leqq 2^{2+1}=8\]
また
\[ S_3=\frac{11}{6}<2<\frac{25}{12}=S_4\]
より$n>3$であるから
\[ 4\leqq n\leqq 7\]
\[ S_4=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}=\frac{25}{12}\]
\[ S_5=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}=\frac{137}{60}\]
\[ S_6=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}=\frac{147}{60}=2+\frac{9}{20}\tag{B}\]
\[ S_7=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}=\frac{1089}{420}=2+\frac{83}{140}\]
よって，$\rm (B)$が条件を満たしているから，$\color{red}(n,m)=(6,9)$が解である．
(3)難易度:★★★★☆
\[ \begin{aligned}A_{20}S_{20}&=A_{20}\sum_{k=1}^{20}\frac{1}{k}=\sum_{k=1}^{20}\frac{A_{20}}{k}\\ &=\sum_{k=1}^{10}\left( \frac{A_{20}}{2k-1}+\frac{A_{20}}{2k}\right) \\ &=\sum_{k=1}^{10}\frac{A_{20}}{2k-1}+\sum_{k=1}^{10}\frac{A_{20}}{2k}\end{aligned}\]
$1$以上$10$以下の整数$k$について，$\frac{A_{20}}{2k-1}$は整数であるから，$\displaystyle \sum_{k=1}^{10}\frac{A_{20}}{2k-1}$は整数．よって，$\displaystyle \sum_{k=1}^{10}\frac{A_{20}}{2k}$について考えればよい．
\[ \begin{aligned}\sum_{k=1}^{10}\frac{A_{20}}{2k}&=\frac{A_{20}}{2}\sum_{k=1}^{10}\frac{1}{k}\\ &=\frac{A_{20}}{2}\left( S_7+\frac{1}{8}+\frac{1}{9}+\frac{1}{10}\right) \\ &=\frac{A_{20}}{2}\left( 2+\frac{83}{140}+\frac{121}{360}\right) \\ &=A_{20}\left( 1+\frac{2341}{2^4\cdot 3^2\cdot 5\cdot 7}\right) \\ &=A_{20}+\frac{1}{16}\cdot \frac{2341A_{20}}{3^2\cdot 5\cdot 7}\end{aligned}\]
$A_20$は整数であるから
\[ \frac{1}{16}\cdot \frac{2341A_{20}}{3^2\cdot 5\cdot 7}\]
を考えると
\[ \begin{aligned}\dfrac{2341A_{20}}{3^2\cdot 5\cdot 7}&=2341\cdot 3\cdot 11\cdot 13\cdot 15\cdot 17\cdot 19\\ &\equiv 5\cdot 3\cdot (-5)\cdot (-3)\cdot (-1)\cdot 1\cdot 3\\ &=15\cdot 15\cdot (-1)\cdot 3\equiv (-1)\cdot (-1)\cdot (-3)\\ &=-3\equiv 13\pmod{16}\end{aligned}\]
したがって，$b=\color{red}{\dfrac{13}{16}}$である．