東京大学 理系 2021年度 第4問 解説
問題編
問題
以下の問いに答えよ。
(1) 正の奇数 $K, L$ と正の整数 $A, B$ が $KA=LB$ を満たしているとする。 $K$ を $4$ で割った余りが $L$ を $4$ で割った余りと等しいならば、 $A$ を $4$ で割った余りは $B$ を $4$ で割った余りと等しいことを示せ。
(2) 正の整数 $a,b$ が $a\gt b$ を満たしているとする。このとき、 $A={}_{4a+1}\mathrm{C}_{4b+1}$, $B={}_a\mathrm{C}_b$ に対して $KA=LB$ となるような正の奇数 $K,L$ が存在することを示せ。
(3) $a,b$ は(2)の通りとし、さらに $a-b$ が $2$ で割り切れるとする。 ${}_{4a+1}\mathrm{C}_{4b+1}$ を $4$ で割った余りは ${}_a\mathrm{C}_b$ を $4$ で割った余りと等しいことを示せ。
(4) ${}_{2021}\mathrm{C}_{37}$ を $4$ で割った余りを求めよ。
考え方
(2)も(3)も説明が難しいです。また、(3)は、流れから考えると「2つの奇数がどのように表されるか」に注目するのでしょうが、これがまた考えづらいです。(4)はおまけみたいな問題です。
解答編
問題
以下の問いに答えよ。
(1) 正の奇数 $K, L$ と正の整数 $A, B$ が $KA=LB$ を満たしているとする。 $K$ を $4$ で割った余りが $L$ を $4$ で割った余りと等しいならば、 $A$ を $4$ で割った余りは $B$ を $4$ で割った余りと等しいことを示せ。
解答例
(1)
$K,A,B$ を $4$ で割ったときの余りを $k,a,b$ とする。仮定より、 $L$ を $4$ で割ったときの余りは $k$ であり、 $k$ は $1$ か $3$ である。また、 $KA$, $LB$ を $4$ で割った余りは、それぞれ、 $ka$, $kb$ を4で割った余りと等しい。これより、 $k(a-b)$ は $4$ で割り切れることがわかる。 $k$ は $1$ か $3$ なので、 $a-b$ は $4$ の倍数となるしかない。よって、 $A, B$ を $4$ で割った余りは等しい。
（終）
解答編 続き
問題
(2) 正の整数 $a,b$ が $a\gt b$ を満たしているとする。このとき、 $A={}_{4a+1}\mathrm{C}_{4b+1}$, $B={}_a\mathrm{C}_b$ に対して $KA=LB$ となるような正の奇数 $K,L$ が存在することを示せ。
解答例
(2)
一般に、正の整数 $m$ に対して $(4m)!$ を考える。
これは、 $1$ から $4m$ までの整数をすべて掛け合わせたものである。この中で、 $4$ の倍数のものだけを抜き出すと\[ 4\cdot1,\ 4\cdot2,\ \cdots,\ 4\cdot m \]なので、これらを掛け合わせると $4^m\cdot m!$ となる。
また、 $1$ から $2n+1$ までの奇数をすべて掛け合わせたものを $(2n+1)!!$ で表すことにすると、 $1$ から $4m$ までのうち、奇数を掛け合わせたものは $(4m-1)!!$ と書ける。また、 $4$ で割って $2$ 余るものは\[
2\cdot 1,\ 2\cdot3,\ 2\cdot 5\ \cdots,\ 2\cdot (2m-1) \]なので、これらを掛け合わせると $2^m\cdot (2m-1)!!$ となる。
以上から、\[ (4m)!=m!2^{3m}(2m-1)!!(4m-1)!! \]と書ける。
$(4a+1)!=(4a+1)\times (4a)!$ であるから
\begin{eqnarray}
A
&=&
{}_{4a+1}\mathrm{C}_{4b+1} \\[5pt]
&=&
\frac{(4a+1)!}{(4b+1)!(4a-4b)!} \\[5pt]
&=&
\frac{a!2^{3a}(2a-1)!!(4a+1)!!}{b!2^{3b}(2b-1)!!(4b+1)!!\cdot (a-b)!2^{3(a-b)}(2a-2b-1)!!(4a-4b-1)!!} \\[5pt]
&=&
{}_a\mathrm{C}_b\cdot \frac{(2a-1)!!(4a+1)!!}{(2b-1)!!(4b+1)!!\cdot (2a-2b-1)!!(4a-4b-1)!!} \\[5pt]
\end{eqnarray}となる。
よって、
\begin{eqnarray}
K &=& (2b-1)!!(4b+1)!!\cdot (2a-2b-1)!!(4a-4b-1)!! \\[5pt]
L &=& (2a-1)!!(4a+1)!!
\end{eqnarray}とすれば、どちらも奇数だけの積なので、 $K, L$ は正の奇数であり、 $KA=LB$ を満たす。よって、問題文にある $K,L$ が存在することが示せた。
（終）
解答編 続き
問題
(3) $a,b$ は(2)の通りとし、さらに $a-b$ が $2$ で割り切れるとする。 ${}_{4a+1}\mathrm{C}_{4b+1}$ を $4$ で割った余りは ${}_a\mathrm{C}_b$ を $4$ で割った余りと等しいことを示せ。
解説
(3)
(2)より、 $K{}_{4a+1}\mathrm{C}_{4b+1}=L{}_a\mathrm{C}_b$ を満たす奇数 $K, L$ は
\begin{eqnarray}
K &=& (2b-1)!!(4b+1)!!\cdot (2a-2b-1)!!(4a-4b-1)!! \\[5pt]
L &=& (2a-1)!!(4a+1)!!
\end{eqnarray}と表すことができるので、これを用いて、 $K,L$ を $4$ で割った余りが等しいことを示す。どちらも奇数の積で表され、 $4$ で割って $1$ 余る数を掛けても $4$ で割った余りは変わらないため、「 $4$ で割って $3$ 余る数」が同じ個数だけ掛けられていることがわかればよい。
$1$ から $4b+1$ までの奇数のうち、 $4$ で割って $3$ 余るものは $b$ 個である。また、 $1$ から $4a-4b-1$ までの奇数のうち、 $4$ で割って $3$ 余るものは $a-b$ 個である。合わせると $a$ 個であり、これは、 $1$ から $4a+1$ までの奇数のうち、 $4$ で割って $3$ 余るものの個数に等しい。
また、 $a$ を偶数とすると、仮定より、 $b$ も偶数である。このとき、 $1$ から $2b-1$ までの奇数のうち、 $4$ で割って $3$ 余るものは $\dfrac{b}{2}$ 個である。また、 $1$ から $2a-2b-1$ までの奇数のうち、 $4$ で割って $3$ 余るものは $\dfrac{a-b}{2}$ 個である。合わせると $\dfrac{a}{2}$ 個であり、これは、 $1$ から $2a-1$ までの奇数のうち、 $4$ で割って $3$ 余るものの個数に等しい。
$a$ が奇数のときは、仮定より、 $b$ も奇数である。このとき、 $1$ から $2b-1$ までの奇数のうち、 $4$ で割って $3$ 余るものは $\dfrac{b-1}{2}$ 個である。また、 $1$ から $2a-2b-1$ までの奇数のうち、 $4$ で割って $3$ 余るものは $\dfrac{a-b}{2}$ 個である。合わせると $\dfrac{a-1}{2}$ 個であり、これは、 $1$ から $2a-1$ までの奇数のうち、 $4$ で割って $3$ 余るものの個数に等しい。
以上から、 $K, L$ を $4$ で割ったときの余りは等しくなる。よって、(1)より、 ${}_{4a+1}\mathrm{C}_{4b+1}$ を $4$ で割った余りは ${}_a\mathrm{C}_b$ を $4$ で割った余りと等しいことがわかる。
（終）
解答編 続き
問題
(4) ${}_{2021}\mathrm{C}_{37}$ を $4$ で割った余りを求めよ。
解答例
(4)
$a=505$, $B=9$ とすると、 $a-b$ は $2$ で割り切れるので、(3)より ${}_{2021}\mathrm{C}_{37}$ を $4$ で割った余りと ${}_{505}\mathrm{C}_{9}$ を $4$ で割った余りは等しい。
また、 $a=126$, $b=2$ とすると、 $a-b$ は $2$ で割り切れるので、(3)より ${}_{505}\mathrm{C}_{9}$ を $4$ で割った余りと ${}_{126}\mathrm{C}_{2}$ を $4$ で割った余りは等しい。
\begin{eqnarray} & & {}_{126}\mathrm{C}_{2} \\[5pt] &=& 63\cdot 125 \\[5pt] &=& (60+3)\cdot (124+1) \\[5pt] \end{eqnarray}なので、 $4$ で割った余りは $3$ となる。以上より、 ${}_{2021}\mathrm{C}_{37}$ を $4$ で割った余りは $3$ である。（終）
