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

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

問題

解答解説

この問題は誘導が良く設計されています．多分，全6問の中で一番面倒な問題であったと思います．が，私はこういう問題の方が得意なので，戦略はすぐにたちました．とはいえ，解答を書くとなると話は別です．

実際，(2) と (3) については長くなってしまったために解答を書き換えました．(オリジナルは感想の後に載せています．)

(1) の解答

この問題は素直に考えましょう．

$K$, $L$ を $4$ で割った商をそれぞれ $p$, $q$, 共通の余りを $r$ とおくと，
$$\begin{array}{rlrl}K& =4p+r& L& =4q+r\end{array}$$
と表すことができます．ここで，$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{array}{rl}{}_{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{array}$$
ここで，$\prod$ という見慣れぬ記号が出てきますが，これは $\sum$ の掛け算版です．この記号を使う方が書くのが簡単で，どのように分子分母を分けたかが分かりやすいので使いました．

上の式は要するに，分子分母にある因数(掛け算の構成要素)を「$4$ の倍数」「$4$ の倍数ではない偶数」「奇数」に分けて，$4$ の倍数同士を $4$ で，$4$の倍数ではない偶数同志を $2$ で約分しています．

これにより，
$$\begin{array}{rl}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{array}$$
とおくと，$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,\dots$ を $4$ で割った余りは $1,3,1,3,\dots$ と交互に現れることから，自然数 $n$ に対して $1,3,\dots ,2n-1$ の中には $4$ で割って $3$ 余る数が $[n/2]$ 個存在します．ここで，$[x]$ は $x$ を超えない最大の整数を表します．

以上のことから，$4$ で割って $3$ 余る数の個数は次のようになります：

• $1,3,\dots ,2b-1$ の中には $[b/2]$ 個
• $1,3,\dots ,2(a-b)-1$ の中には $[(a-b)/2]=(a-b)/2$個 ($a-b$ は $2$ の倍数より)
• $1,3,\dots ,4b+1$ の中には $[(2b+1)/2]=b$個
• $1,3,\dots ,4(a-b)-1$ の中には $[2(a-b)/2]=a-b$個
• $1,3,\dots ,2a-1$ の中には $[a/2]$個
• $1,3,\dots ,4a+1$ の中には $[(2a+1)/2]=a$個

したがって，$K$ と $L$ の中の $4$ で割って $3$ 余る因数の個数をそれぞれ $M$ と $N$ で表すと，
$$\begin{array}{rl}M& =[b/2]+(a-b)/2+b+(a-b)\\ N& =[a/2]+a\end{array}$$
となるので，$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{array}{rl}{}_{2021}{\mathrm{C}}_{37}& \equiv {}_{4\times 505+1}{\mathrm{C}}_{4\times 9+1}\equiv {}_{505}{\mathrm{C}}_9\equiv {}_{4\times 126+1}{\mathrm{C}}_{4\times 2+1}\\ & \equiv {}_{126}{\mathrm{C}}_2=126\times 125\mathbf{\nabla }\mathbf{\cdot }2\equiv 3\times 1\equiv 3(\mathrm{mod}4)\end{array}$$
であるので，余りは $3$ となります．

感想

小問 (2) と (3) は当初の証明から変更しました．アイデアは同じですが，上記のように $K$ と $L$ を直接求める方が記述が簡単になるからです．

ですが，当初の証明の方が私の思考が伝わると思うので，かなり恥ずかしい代物ですが敢えて残しておきます．

しかし，この問題は入試としてはかなりタフだと思います．特に (3) は時間内で解くのが厳しい．(1), (2), (4) くらいが限界のような気がします．

問題としてはなかなかに意欲的で，面白い問題だと思います．少し泥臭いことを要求しますが，このくらいはありだと思いますし，それほど汚い感じはしませんでした．

別解(当初の証明)

(2) の解答

$A$ と $B$ が因数として $2$ をいくつ持つかを数えれば終わりです．
$$\begin{array}{rl}A& =2^{p}L\\ B& =2^{q}K\end{array}$$
と表すとします．ここで，$p$, $q$ は非負整数で，$L$, $K$ は正の奇数であるとします．このとき，$p$ = $q$ が成立すれば $KA=LB=2^{p}KL$ が成り立つので，以下では $A$ と $B$ に含まれる 因数 $2$ の個数が等しいことを示します．

自然数 $n$ に対して $n!$ に含まれる因数 $2$ の個数を $Z(n)$ とします．このとき，次の補題が成り立ちます．

ここで、
$$\begin{array}{rl}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{array}$$
であるので、$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{array}{rl}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{array}$$
であるので，
$$\begin{array}{rl}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{array}$$
が成立し，$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))\}mod2$，$K$ に含まれる $4$ で割って $3$ 余る因数の個数の偶奇は $\{X(a)-X(b)-X(a-b)\}mod2$ であるので，以下では
$$X(4a+1)-X(4b+1)-X(4(a-b))\equiv X(a)-X(b)-X(a-b)(\mathrm{mod}2)$$
であることを示します．

補題 2 より
$$\begin{array}{rl}X(4a+1)& \equiv X(2a)+[(2a+2)/2]\equiv X(a)+[a/2]+a+1(\mathrm{mod}2)\\ X(4b+1)& \equiv X(b)+[b/2]+b+1(\mathrm{mod}2)\\ X(4(a-b))& \equiv X(2(a-b))+(a-b)\equiv X(a-b)+[(a-b)/2]+(a-b)(\mathrm{mod}2)\end{array}$$
となるので，
$$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](\mathrm{mod}2)$$
ここで，$a-b$ が $2$ の倍数であるので，$[a/2]-[b/2]=(a-b)/2$ かつ $[(a-b)/2]=(a-b)/2$ となり，
$$\begin{array}{rl}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)(\mathrm{mod}2)\end{array}$$
となります．

したがって，$K$ と $L$ を $4$ で割った余りは等しいので，$A$ と $B$ も $4$ で割った余りが等しいことが証明されました．