【東京大学2021年度入試数学(理系)第4問】解答の難しい整数問題

今回は2021を盛り込んだ整数問題です．今年出題された6問の中でも最も面白い問題です．

問題

解答解説

この問題は誘導が良く設計されています．多分，全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)$ とします．このとき，次の補題が成り立ちます．

ここで、
\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)$ で表します．このとき，次の性質が成り立ちます．

$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$ で割った余りが等しいことが証明されました．