年号を織り込んだ問題 – 2021年東大 数学 第4問
2021年東大 数学 第4問 は、年号を織り込んだ問題です。東大においてこの手の問題は過去にも出題されたことがありますが、こちらのほうが難しい印象です。
問題文は以下の通りです。
以下の問いに答えよ。
(1) 正の奇数 K,L と正の整数 A,B が KA = LB を満たしているとする。 K を4で割った余りが L を4で割った余りと等しいならば、 A を4で割った余りは B を4で割った余りと等しいことを示せ。
(2) 正の整数 a, b が a > 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で割った余りを求めよ。
小問が4つもあってなんか嫌げな感じです。しかし、一般に小問は結論に導くための誘導であることが多いので、初めのほうの小問は簡単であることが期待できます。実際の試験では、部分点を狙ってとりあえず小問1はチェックしてみましょう。
小問１の解法
実際、小問1はそれほど難しくありません。題意より、 K,L を4で割った余りは等しいので、これを \gamma と置くと、 K,L は奇数なので、 \gamma は１か３のいずれかです。
また正の整数 A,B を4で割った余りをそれぞれ、 \alpha, \beta と置きます。 \alpha, \beta は０，１，２，３のいずれかです。
KA = LB なので、上記の式をこれに代入して、
\alpha \gamma \equiv \beta \gamma \pmod 4
ですが、両辺に \gamma をかけると
\alpha \gamma^2 \equiv \beta \gamma^2 \pmod 4
です。ところが、 \gamma は1か3のいずれかなので、 \gamma^2 \equiv 1 \pmod 4 です。ゆえに、
\alpha \equiv \beta \pmod 4
ですが、 \alpha, \beta は０，１，２，３のいずれかなので、上記の式が成り立つためには \alpha = \beta であることが必要です。ゆえに、 A,B の余りは等しくなります。
小問２の解法
実は、各小問のなかでこれが一番難しいです。
KA = LB が成り立つなら、
\frac{A}{B}= \frac{\text{奇数}}{ \text{奇数} } となるはずです。ここからの発想で、 \frac{A}{B} を約分していって、その結果が \frac{\text{奇数}}{ \text{奇数} } になることを示します。これが示せれば、分母、分子をそれぞれ K,L と置くことで、題意が証明できたことになります。
そういうわけで、 \frac{A}{B} を計算してみます。
\begin{aligned}
& \frac{A}{B} = \frac{ {}_{4a+1} \mathrm{C}_{4b+1}}{{}_{a} \mathrm{C}_{b}} \\
& = \frac{\frac{(4a+1)!}{(4b+1)!(4a-4b)!}}{\frac{a!}{b!(a-b)!}} \\
& = \frac{\frac{(4a+1)!}{a!}}{\frac{(4b+1)!}{b!} \cdot \frac{(4a-4b)!}{(a-b)!}} \\
\end{aligned}ここで自然数 n に対し、
\begin{aligned}
& \frac{4n!}{n!} = \prod_{k=1}^n \frac{4k(4k-1)(4k-2)(4k-3)}{k} \\
& = \prod_{k=1}^n 4(4k-1)(4k-2)(4k-3) \\
& = 8^n\prod_{k=1}^n (4k-1)(2k-1)(4k-3) \\
\end{aligned}が成り立ちます。そこで、自然数 n の関数 f(n) を
\begin{aligned}
& f(n) = \prod_{k=1}^n (4k-1)(2k-1)(4k-3)
\end{aligned}と定義すると、すべての n に対し、 f(n) は奇数です。（！）
以上より、
\begin{aligned}
& \frac{A}{B} = \frac{ 8^{a}(4a+1)f(a)}{ 8^{b}(4b+1)f(b) \cdot 8^{a-b}f(a-b)} \\
& \text{ } = \frac{ (4a+1)f(a)}{ (4b+1)f(b)f(a-b)} \\
\end{aligned}を得ますが、ここで
\begin{aligned}
& L = (4a+1)f(a)\\
& K = (4b+1)f(b)f(a-b) \\
\end{aligned}とおくと、 K,L は奇数であり、かつ KA = LB を満たします。
以上、小問2が証明できました。
小問３の解法
問題文から、小問1の結果を応用することを思いつけます。そこで、 K \equiv L \pmod 4 を証明することを考えます。
f(n) を4で割った余り
最初に、小問2で定義した
\begin{aligned}
& f(n) = \prod_{k=1}^n (4k-1)(2k-1)(4k-3)
\end{aligned}を4で割った余りが何であるか、調べます。
すべての自然数 k に対し、
\begin{aligned}
& (4k-1)(4k-3) \\
&= 16k^2- 16k +3 \\
& \equiv 3 \pmod 4
\end{aligned}です。また、
2k-1 \equiv \left \{
\begin{aligned}
& 3 (k\text{が偶数})\\
&1(k\text{が奇数})
\end{aligned}
\right .
\pmod 4となります。
したがって、 3^2 \equiv 1 \pmod 4 であることに注意すると、 n = 4m+l ( m は非負整数、 l は1,2,3,4のいずれか）と置くとき、
\begin{aligned}
& f(n) \\
& =f(4m+l) \\
&= \prod_{k=1}^{4m+l}(4k-1)(2k-1)(4k-3) \\
& = \prod_{k=1}^{4m+l} (4k-1)(4k-3) \prod_{k=1}^{4m+l} (2k-1)\\
& = \prod_{k=1}^{4m+l} (4k-1)(4k-3) \\
& \times \prod_{\substack{1 \leqq k \leqq 4m+l \\ k \text{が偶数}}} (2k-1) \prod_{\substack{1 \leqq k \leqq 4m+l \\ k \text{が奇数}}} (2k-1)\\
& \equiv 3^{4m+l} \cdot 3^{2m+[\frac{l}{2}]} \\
& \equiv 3^{l+[\frac{l}{2}]} \\
& \equiv \left \{
\begin{aligned}
& 3^{1+0} \equiv 3(l=1)\\
& 3^{2+1} \equiv 3(l=2)\\
& 3^{3+1} \equiv 1(l =3)\\
& 3^{4+2} \equiv 1(l=4)\\
\end{aligned}
\right .
\pmod 4
\end{aligned}ここに、 [] はガウスの記号です。
よって、
\begin{aligned}
& f(n) \equiv \left \{
\begin{aligned}
& 3(n=4m+1)\\
& 3(n=4m+2)\\
& 1(n=4m+3)\\
& 1(n=4m+4)\\
\end{aligned}
\right .
\pmod 4 \\
& \text{ } (m\text{は非負整数})
\end{aligned}です。
f(n) における n の縮減公式
上式から、自然数 k,l が k \equiv l \pmod 4 であるとき、
f(k) \equiv f(l) \pmod 4
であることが示せます。これからただちに、すべての自然数 n,m に対して
\begin{aligned}
f(n +4m) \equiv f(n) \pmod 4\\
\end{aligned}が成り立つことを導出できます。
また、 n=4i+j （ i は非負整数、 j は１，２，３，４のいずれか）とするとき、
\begin{aligned}
& f(n+4m +2) \\
& = f(4i + j + 4m+2) \\
& \equiv f(j +2) \pmod 4 \\
& \equiv 3f(j) \pmod 4 \\
& \equiv 3f(4i + j) \pmod 4 \\
& \equiv 3f(n) \pmod 4 \\
\end{aligned}
が成り立ちます。ここで f(j+2) \equiv 3f(j) が成り立つことは、以下のようにして示せます。
\begin{aligned}
& f(1+2) = f(3) \\
&\equiv 1 \equiv 3^2 \equiv 3f(1) \pmod 4 \\
& f(2+2) = f(4) \\
&\equiv 1 \equiv 3^2 \equiv 3f(2) \pmod 4 \\
& f(3+2) = f(5) \\
&\equiv f(1) \equiv 3 \equiv 3f(3) \pmod 4 \\
& f(4+2) = f(6) \\
&\equiv f(2) \equiv 3 \equiv 3f(4) \pmod 4 \\
\end{aligned}K,L を4で割った余りが等しいことの証明
a-b が偶数であるという条件ですが、 a-b が4で割り切れるすなわち a-b = 4m ( m は自然数）のとき、
f(a-b) \equiv 1 \pmod 4
です。また、
\begin{aligned}
& f(a) = f(b+4m) \\
& \text{ } \equiv f(b) \pmod 4
\end{aligned}が成り立ち、ゆえに
\begin{aligned}
& K = (4a+1)f(a) \\
& = (4a+1)f(b+4m) \\
&\equiv f(b) \pmod 4\\
& \equiv f(b)f(a-b) \pmod 4\\
& \equiv L \pmod 4
\end{aligned}が成り立ちます。
次に、 a-b を4で割った余りが2すなわち a-b = 4m +2 ( m は非負整数）のとき、
f(a-b) \equiv 3 \pmod 4
です。また、
\begin{aligned}
& f(a) =f(b+4m + 2) \\
& \text{ } \equiv3 f(b) \pmod 4
\end{aligned}が成り立ち、ゆえに
\begin{aligned}
& K = (4a+1)f(a) \\
& = (4a+1)f(b+4m+2) \\
&\equiv 3f(b) \pmod 4\\
& \equiv f(b)f(a-b) \pmod 4\\
& \equiv L \pmod 4
\end{aligned}が成り立ちます。以上の結果に小問1の結果を適用することにより、小問3が証明できました。
小問４の解法
これが一番簡単で、小問3の結果を適用するだけです。
\begin{aligned}
& {}_{2021} \mathrm{C}_{37} \\
& = {}_{4 \times505 +1} \mathrm{C}_{4 \times 9 +1} \\
& \equiv {}_{505} \mathrm{C}_{9 } \pmod 4 \\
& = {}_{4 \times 126 +1} \mathrm{C}_{4 \times 2 +1} \\
& \equiv {}_{ 126} \mathrm{C}_{ 2 } \pmod 4 \\
& = 63 \times 125 \equiv 3 \pmod 4
\end{aligned}すなわち、余りは3です。
解法のポイント
小問2で以下の式(1)
\frac{A}{B}= \frac{\text{奇数}}{ \text{奇数} } \cdots(1)が成り立つことを、実際に以下の式(2)を計算して証明しようと思いつくことがポイントです。
\begin{aligned}
& \frac{A}{B} = \frac{ {}_{4a+1} \mathrm{C}_{4b+1}}{{}_{a} \mathrm{C}_{b}} \\
& = \frac{\frac{(4a+1)!}{(4b+1)!(4a-4b)!}}{\frac{a!}{b!(a-b)!}} \\
& = \frac{\frac{(4a+1)!}{a!}}{\frac{(4b+1)!}{b!} \cdot \frac{(4a-4b)!}{(a-b)!}} \cdots(2)\\
\end{aligned}しかし、 A,B の具体的な式が与えられているので、 K,L も具体的な例を生成してみようと考えられれば、無理なくたどり着けることと思います。
一般に、「××が存在することを示せ」と言われたときは、具体的な例を１つ提示できればOKです。まずは具体例を生成できないか、検討するようにして見てください。