年号を絡めた二項係数の偶奇判定 – 2015年東大数学第5問

2024年12月9日

　年号組み合わせ数の偶奇判定 – 2015年東大数学第5問は年号を絡めた二項係数 _nC_r に対する偶奇判定の問題です。問題文は以下のとおりで、東大2次試験からの引用です。

m を 2015 以下の正の整数とする．₂₀₁₅C_m が偶数となる最小の m を求めよ．

　二項係数ってたいてい偶数なのでは、と思いましたが、こういう問題が出るということはそうではないようです。問題文自体はシンプルだし、案外何とかなるかもしれません。それでは見ていきます。なお、本稿の内容は東大が発表したものではありません。

2015年東大数学第5問の解法

　本当に偶数にならないのか、いくつかの m について確認してみます。

\begin{aligned} _{2015} \mathrm{C}_2 = & \frac{2015 \times 2014}{2 \times 1} = 2015 \times 1007 \\ _{2015} \mathrm{C}_3 = & \frac{2015 \times 2014 \times 2013}{ 3 \times 2 \times 1} \\ = &2015 \times 1007 \times 2013\\ _{2015} \mathrm{C}_4 = & \frac{2015 \times 2014 \times 2013 \times 2012}{ 4 \times 3 \times 2 \times 1} \\ = &2015 \times 1007 \times 2013 \times 503\\ \end{aligned}

　なるほど。確かになかなか偶数になりません。

　偶数にならないのは素因数2の数が分母と分子で同じだからですが、ここで

_{2015} \mathrm{C}_m = \prod_{k=1} ^m \frac{2016-k}{k}

と表記してみると、 k が奇数なら 2016 – k も奇数なので、₂₀₁₅C_m が偶数になるかどうかの判定は k が偶数の場合だけを考えれば良いことがわかります。

　k が偶数のとき、 $\displaystyle\frac{2026-k }k$ を2で約分しきったあとで分母に２が残っていると面倒くさいので、どういうときにそんなことが起きるかを考えます。

　2016 = 2⁵・7・9 なので、 k = 2ⁿl （ l は奇数）と置くと、 n ≦ 4 のとき

2016 - k = 2^n(2^{5-n} \cdot 63 -l)

なので、約分したあと分母に2は残りません。分子の方は約分したあとの 2^5-n・63 – l が奇数なので、やはり素因数に2は残りません。

　 n = 5 のとき、

2016 - k = 2^5(63 -l)

ですが、 63 –l は偶数なので約分したあと分子に2が残ります。 32 ≦ m ならば k = 2⁵l となるk (1 ≦ k ≦ m) が存在するので、 ₂₀₁₅C_m が偶数になる可能性が出てきました。

　逆に言うと m ≦ 31 のとき、 m 以下の正の偶数 k における 2 の次数 n は 4 以下なので、 ₂₀₁₅C_m は奇数です。この対偶をとることで、 ₂₀₁₅C_m が偶数であるための必要条件は 32 ≦ m であることがわかりました。

　なお、 n≧ 6 の場合は最早どうでもいいので、深追いしません。

　一方 m = 32 のとき、

_{2015} \mathrm{C}_{32} = \prod_{k=1} ^{32} \frac{2016-k}{k}

において k ≦ 31 のとき、先に見たように $\displaystyle\frac{2016-k }k$ を約分したあとに素因数２は分母にも分子にも残りません。 $\displaystyle\frac{2026-32 }{32} = 62$ なので、 ₂₀₁₅C₃₂ は偶数です。

　ゆえに求める m は32です。

　₂₀₁₅C_m がどういうときに偶数になるのかを二項係数の定義に照らして考えていけば、比較的容易に回答にたどり着けると思います。

　2で約分した結果を評価したいのと、二項係数の分母も分子も偶数は1つおきにしか現れないことから、分母分子を偶数同士のセットにしようという発想が思いつければ答えは目前です。他の素数の場合にも応用できるので、考え方を覚えておくようにしましょう。