【東京大学2021年度入試数学(理系)第4問】解答の難しい整数問題
今回は2021を盛り込んだ整数問題です．今年出題された6問の中でも最も面白い問題です．
問題
以下の問いに答えよ。
正の奇数 $K$, $L$ と正の整数 $A$, $B$ が $KA = LB$ を満たしているとする。$K$ を $4$ で割った余りが $L$ を $4$ で割った余りに等しいならば，$A$ を $4$ で割った余りは $B$ を $4$ で割った余りと等しいことを示せ。
正の整数 $a$, $b$ が $a > b$ を満たしているとする。このとき，$A = {}_{4a+1}\mathrm{C}_{4b+1}$, $B = {}_{a}\mathrm{C}_{b}$ に対して $KA = LB$ となるような正の整数 $K$, $L$ が存在することを示せ。
$a$, $b$ は (2) の通りとし，さらに $a - b$ が $2$ の倍数で割り切れるとする。${}_{4a+1}\mathrm{C}_{4b+1}$ を $4$ で割った余りは $_{a}\mathrm{C}_{b}$ を $4$ で割った余りと等しいことを示せ。
${}_{2021}\mathrm{C}_{37}$ を $4$ で割った余りを求めよ。
解答解説
この問題は誘導が良く設計されています．多分，全6問の中で一番面倒な問題であったと思います．が，私はこういう問題の方が得意なので，戦略はすぐにたちました．とはいえ，解答を書くとなると話は別です．
実際，(2) と (3) については長くなってしまったために解答を書き換えました．(オリジナルは感想の後に載せています．)
(1) の解答
この問題は素直に考えましょう．
$K$, $L$ を $4$ で割った商をそれぞれ $p$, $q$, 共通の余りを $r$ とおくと，
\begin{align}
K &= 4p + r&
L &= 4q + r
\end{align}
と表すことができます．ここで，$K$ と $L$ は奇数であり，$r$ は $K$, $L$ を $4$ で割った余りであるので，$r = 1$ もしくは $r = 3$ となります．
$KA = LB$ より $(4p + r)A = (4q + r)B$ すなわち $r(A - B) = 4(qB - pA)$ となりますが，$p$, $q$, $r$, $A$, $B$ は全て整数であることから，右辺は 4 の倍数で，$r$ と $4$ は互いに素であるので，$A - B$ は4の倍数となります．
すなわち，$A$ を $4$ で割った余りと $B$ を $4$ で割った余りは等しいことが証明されました．
(2) の解答
${}_{4a+1}\mathrm{C}_{4b+1}$ を式変形していきます．
\begin{align}
{}_{4a+1}\mathrm{C}_{4b+1}
&=\frac{(4a+1)!}{(4b+1)!\times\{4(a-b)\}!}\\
&=\frac{(4a+1)4a(4a-1)\cdots 1}{(4b+1)4b(4b-1)\cdots 1\times 4(a-b)\{4(a-b)-1\}\cdots 1}\\
&=\frac{\displaystyle\prod_{i=1}^{a}(4i)}{\displaystyle\prod_{i=1}^{b}(4i)\times\prod_{i=1}^{a-b}(4i)}\times\frac{\displaystyle\prod_{i=1}^{a}\{2(2i-1)\}}{\displaystyle\prod_{i=1}^{b}\{2(2i-1)\}\times\prod_{i=1}^{a-b}\{2(2i-1)\}}\times\frac{\displaystyle\prod_{i=1}^{2a+1}(2i-1)}{\displaystyle\prod_{i=1}^{2b+1}(2i-1)\times\prod_{i=1}^{2(a-b)}2(2i-1)}\\
&=\frac{\displaystyle\prod_{i=1}^{a}i}{\displaystyle\prod_{i=1}^{b}i\times\prod_{i=1}^{a-b}i}\times\frac{\displaystyle\prod_{i=1}^{a}(2i-1)}{\displaystyle\prod_{i=1}^{b}(2i-1)\times\prod_{i=1}^{a-b}(2i-1)}\times\frac{\displaystyle\prod_{i=1}^{2a+1}(2i-1)}{\displaystyle\prod_{i=1}^{2b+1}(2i-1)\times\prod_{i=1}^{2(a-b)}2(2i-1)}\\
&={}_{a}\mathrm{C}_{b}\times\frac{\displaystyle\prod_{i=1}^{a}(2i-1)}{\displaystyle\prod_{i=1}^{b}(2i-1)\times\prod_{i=1}^{a-b}(2i-1)}\times\frac{\displaystyle\prod_{i=1}^{2a+1}(2i-1)}{\displaystyle\prod_{i=1}^{2b+1}(2i-1)\times\prod_{i=1}^{2(a-b)}2(2i-1)}
\end{align}
ここで，$\prod$ という見慣れぬ記号が出てきますが，これは $\sum$ の掛け算版です．この記号を使う方が書くのが簡単で，どのように分子分母を分けたかが分かりやすいので使いました．
上の式は要するに，分子分母にある因数(掛け算の構成要素)を「$4$ の倍数」「$4$ の倍数ではない偶数」「奇数」に分けて，$4$ の倍数同士を $4$ で，$4$の倍数ではない偶数同志を $2$ で約分しています．
これにより，
\begin{align}
K&=\prod_{i=1}^{b}(2i-1)\prod_{i=1}^{a-b}(2i-1)\prod_{i=1}^{2b+1}(2i-1)\prod_{i=1}^{2(a-b)}(2i-1)\\
L&=\prod_{i=1}^{a}(2i-1)\prod_{i=1}^{2a+1}(2i-1)
\end{align}
とおくと，$K$ と $L$ はそれぞれ奇数であり，上式より $\displaystyle A=B\times\frac{L}{K}$ すなわち $KA = LB$ が成立するのは明らかなので，これが条件を満たす $K$ と $L$ になります．
(3) の解答
$K$ を $4$ で割った余りと $L$ を $4$ で割った余りが等しければ，(1) より命題が成立することになります．
$m$, $n$ が整数であるとき，
- $(4m + 1)(4n + 1) = 4(4mn + m + n) + 1$
- $(4m + 1)(4n + 3) = 4(4mn + 3m + n) + 3$
- $(4m + 3)(4n + 3) = 4(4mn + 3m + 3n + 2) + 1$
したがって，奇数のみからなる積は，積に含まれる $4$ で割って $3$ 余る因数の個数が偶数のときは $4$ で割って $1$ 余り，奇数のときは $4$ で割って $3$ 余ります．よって，$K$ に含まれる $4$ で割って $3$ 余る因数の個数と $L$ に含まれる $4$ で割って $3$ 余る因数の個数の偶奇が等しいことを証明すれば十分となります．
では、$K$ と $L$ の因数の中に $4$ で割って $3$ 余る数が何個あるかを数えましょう．
$1, 3, 5, 7, \ldots$ を $4$ で割った余りは $1, 3, 1, 3, \ldots$ と交互に現れることから，自然数 $n$ に対して $1, 3, \ldots, 2n-1$ の中には $4$ で割って $3$ 余る数が $[n/2]$ 個存在します．ここで，$[x]$ は $x$ を超えない最大の整数を表します．
以上のことから，$4$ で割って $3$ 余る数の個数は次のようになります：
- $1, 3, \ldots, 2b - 1$ の中には $[b/2]$ 個
- $1, 3, \ldots, 2(a-b) - 1$ の中には $[(a-b)/2] = (a-b)/2$個 ($a-b$ は $2$ の倍数より)
- $1, 3, \ldots, 4b + 1$ の中には $[(2b + 1)/2] = b$個
- $1, 3, \ldots, 4(a-b) - 1$ の中には $[2(a-b)/2] = a-b$個
- $1, 3, \ldots, 2a - 1$ の中には $[a/2]$個
- $1, 3, \ldots, 4a + 1$ の中には $[(2a + 1)/2] = a$個
したがって，$K$ と $L$ の中の $4$ で割って $3$ 余る因数の個数をそれぞれ $M$ と $N$ で表すと，
\begin{align}
M &=[b/2] + (a-b)/2 + b + (a-b)\\
N &=[a/2] + a
\end{align}
となるので，$N - M = [a/2] - [b/2] - (a-b)/2$ となります．ここで，$a - b$ は $2$ の倍数であることより，$a$ と $b$ の偶奇は一致するため，$[a/2] - [b/2] = (a-b)/2$ となります．したがって，$N - M = 0$ すなわち $M = N$ となり，$M$ と $N$ の偶奇も一致したため，命題が証明されました．
(4) の解答
単に計算問題です．
\begin{align}
{}_{2021}\mathrm{C}_{37}
&\equiv {}_{4×505+1}\mathrm{C}_{4×9+1} \equiv {}_{505}\mathrm{C}_{9} \equiv {}_{4×126+1}\mathrm{C}_{4×2+1}\\
&\equiv {}_{126}\mathrm{C}_{2} = 126\times 125 \div 2 \equiv 3 \times 1 \equiv 3 \pmod{4}
\end{align}
であるので，余りは $3$ となります．
感想
小問 (2) と (3) は当初の証明から変更しました．アイデアは同じですが，上記のように $K$ と $L$ を直接求める方が記述が簡単になるからです．
ですが，当初の証明の方が私の思考が伝わると思うので，かなり恥ずかしい代物ですが敢えて残しておきます．
しかし，この問題は入試としてはかなりタフだと思います．特に (3) は時間内で解くのが厳しい．(1), (2), (4) くらいが限界のような気がします．
問題としてはなかなかに意欲的で，面白い問題だと思います．少し泥臭いことを要求しますが，このくらいはありだと思いますし，それほど汚い感じはしませんでした．
別解(当初の証明)
(2) の解答
$A$ と $B$ が因数として $2$ をいくつ持つかを数えれば終わりです．
\begin{align}
A &= 2^p L\\
B &= 2^q K
\end{align}
と表すとします．ここで，$p$, $q$ は非負整数で，$L$, $K$ は正の奇数であるとします．このとき，$p$ = $q$ が成立すれば $KA = LB = 2^p KL$ が成り立つので，以下では $A$ と $B$ に含まれる 因数 $2$ の個数が等しいことを示します．
自然数 $n$ に対して $n!$ に含まれる因数 $2$ の個数を $Z(n)$ とします．このとき，次の補題が成り立ちます．
$Z(2n+1) = Z(2n) = Z(n) + n$
$2n + 1$ は奇数であるので，$Z(2n+1) = Z(2n)$ は明らかです．$1, 2, \ldots, 2n$ の中で因数 $2$ を含むのは偶数である $2, 4, \ldots, 2n$ のみで，これらすべてを $2$ で割ると $1, 2, \ldots, n$ が得られます．したがって，$1$ ～ $n$ までの中に含まれる因数 $2$ の個数 $Z(n)$ に，各偶数から $1$ 個ずつ取り除いた因数 $2$ の個数の合計 $n$ を加えた数が $Z(2n)$ になります．
ここで、
\begin{align}
A &= {}_{4a+1}\mathrm{C}_{4b+1} = \displaystyle\frac{(4a+1)!}{(4b+1)! \times \{4(a-b)\}!}\\
B &= {}_{a}\mathrm{C}_{b} = \displaystyle\frac{a!}{b!\times (a-b)!}
\end{align}
であるので、$A$ に含まれる因数 $2$ の個数 $p = Z(4a+1) - Z(4b+1) - Z(4(a-b))$，$B$ に含まれる因数 $2$ の個数 $q = Z(a) - Z(b) - Z(a-b)$ となりますが，補題1より
\begin{align}
Z(4a+1) &= Z(2a) + 2a = Z(a) + 3a\\
Z(4b+1) &= Z(b) + 3b\\
Z(4(a-b)) &=Z(a-b) - 3(a-b)
\end{align}
であるので，
\begin{align}
p &= Z(4a+1) - Z(4b+1) - Z(4(a-b))\\
&= Z(a) + 3a - Z(b) - 3b - Z(a-b) - 3(a-b)\\
&= Z(a) - Z(b) - Z(a-b) = q
\end{align}
が成立し，$p = q$ が証明されました．
(3) の解答
前問より $A = 2^p L$ かつ $B = 2^p K$ であることが示されたので，(3) では $L$ に含まれる ($A$ に含まれる) 因数で $4$ で割って $3$ 余る数の個数と，$K$ に含まれる($B$ に含まれる) 因数で $4$ で割って $3$ 余る数の個数を数えます．ただし、その偶奇だけが等しければ十分です．
というのも，$2$つの奇数をかけるとき，$4$ で割った余りの組合せは $(1,1)$, $(1,3)$, $(3,1)$, $(3,3)$ の $4$ 通りありますが，$(1, 1)$ と $(3, 3)$ のときは積を $4$ で割ると余りが $1$ となり，$(3, 1)$ と $(1, 3)$ のときは積を $4$ で割ると余りが $3$ となります．
ということは，奇数因数の積を $4$ で割るとき，$4$ で割って余りが $3$ である因数が偶数個であれば余りが $1$ に，奇数個であれば余りが $3$ になります．また，割り算に関しても同様です．
小問 (2) と同じように $n!$ に含まれる $4$ で割って $3$ 余る奇数因数の個数の偶奇を $X(n)$ で表します．このとき，次の性質が成り立ちます．
任意の正の整数 $n$ に対して
\begin{align}
X(2n) &\equiv X(n) + [n/2] \pmod{2}\\
X(2n+1) &\equiv X(n) + [(n+1)/2] \pmod{2}
\end{align}
ここで，$[x]$ は $x$ を超えない最大の整数とします．
$1, 2, \ldots, 2n$ を偶奇で分けます．
偶数部分 $2, 4, \ldots, 2n$ に含まれる奇数因数は，これらを $2$ で割った $1, 2, \ldots, n$ に含まれる奇数因数と等しいため，この中で $4$ で割って $3$ 余る奇数因数の個数の偶奇は $X(n)$ に等しくなります．
一方，奇数部分 $1, 3, \ldots, 2n -1$ は $4$ で割ると $1, 3, 1, 3, \ldots$ となるので，余りが $3$ となる個数は $[n/2]$ となります．
よって，$X(2n)$ の式は正しいことが示されました．$X(2n+1)$ も同様です．
$L$ に含まれる $4$ で割って $3$ 余る因数の個数の偶奇は $\{X(4a+1)-X(4b+1)-X(4(a-b))\}\bmod 2$，$K$ に含まれる $4$ で割って $3$ 余る因数の個数の偶奇は $\{X(a)-X(b)-X(a-b)\}\bmod 2$ であるので，以下では
\begin{equation}
X(4a+1)-X(4b+1)-X(4(a-b))\equiv X(a)-X(b)-X(a-b)\pmod{2}
\end{equation}
であることを示します．
補題 2 より
\begin{align}
X(4a+1) &\equiv X(2a) + [(2a+2)/2] \equiv X(a) + [a/2] + a + 1 \pmod{2}\\
X(4b+1) &\equiv X(b) + [b/2] + b + 1 \pmod{2}\\
X(4(a-b)) &\equiv X(2(a-b)) + (a-b)\equiv X(a-b) + [(a-b)/2] + (a-b) \pmod{2}
\end{align}
となるので，
\begin{equation}
X(4a+1) - X(4b+1) - X(4(a-b))\equiv X(a) - X(b) - X(a-b) + [a/2] - [b/2] - [(a-b)/2] \pmod{2}
\end{equation}
ここで，$a-b$ が $2$ の倍数であるので，$[a/2] - [b/2] = (a-b)/2$ かつ $[(a-b)/2] = (a-b)/2$ となり，
\begin{align}
X(4a+1) - X(4b+1) - X(4(a-b))
&\equiv X(a) - X(b) - X(a-b) + \frac{a-b}{2}-\frac{a-b}{2}\\
&\equiv X(a) - X(b) - X(a-b) \pmod{2}
\end{align}
となります．
したがって，$K$ と $L$ を $4$ で割った余りは等しいので，$A$ と $B$ も $4$ で割った余りが等しいことが証明されました．