2015Cmが偶数になる最小のm(東京大学2015年前期理系数学第5問)

2015年の二項係数に関する東大の整数問題を取り上げます。誘導が全く無い一行問題ということもあり、この年で一番話題になった整数問題と言っても良いでしょう。こういう問題はワクワクしますね!(笑)


《問題》

$m$を$2015$以下の正の整数とする。${}_{2015}\mathrm{C}_m$が偶数となる最小の$m$を求めよ。

(東京大学2015年 前期理系第5問)


《考え方》

まずは小さい$m$で実験しましょう。

$m=1,\,2,\,3,\,4,\,\cdots$ とすると、$$\small \begin{array}{l}
{ }_{2015}\mathrm{C}_{1}=\dfrac{2015}{1} \\
{ }_{2015}\mathrm{C}_{2}=\dfrac{2015}{1} \cdot \dfrac{2014}{2} \\
{ }_{2015}\mathrm{C}_{3}=\dfrac{2015}{1} \cdot \dfrac{2014}{2} \cdot \dfrac{2013}{3} \\
{ }_{2015}\mathrm{C}_{4}=\dfrac{2015}{1} \cdot \dfrac{2014}{2} \cdot \dfrac{2013}{3} \cdot \dfrac{2012}{4}
\end{array}$$となり、${}_{2015}\mathrm{C}_m$が偶数となるためには最後の$\dfrac{2016-m}{m}$が偶数である必要がありそうです(必要条件)。

$m$は${}_{2015}\mathrm{C}_m$が偶数となる最小の整数なので、$1 \leqq k < m$ を満たす整数$k$について${}_{2015}\mathrm{C}_k$はすべて奇数です。したがって$\dfrac{2016-m}{m}$が偶数になるような最小の整数$m$が求めるものだと分かります。

●   ●   ●

解答例

$m=1,\,2,\,3\,4,\,\cdots$ とすると、$$\small \begin{array}{l}
{ }_{2015}\mathrm{C}_{1}=\dfrac{2015}{1} \\
{ }_{2015}\mathrm{C}_{2}=\dfrac{2015}{1} \cdot \dfrac{2014}{2} \\
{ }_{2015}\mathrm{C}_{3}=\dfrac{2015}{1} \cdot \dfrac{2014}{2} \cdot \dfrac{2013}{3} \\
{ }_{2015}\mathrm{C}_{4}=\dfrac{2015}{1} \cdot \dfrac{2014}{2} \cdot \dfrac{2013}{3} \cdot \dfrac{2012}{4}
\end{array}$$となるから、$m$を大きくしていくとき${ }_{2015}\mathrm{C}_{m}$が初めて偶数となるのは$m$が偶数であるときである。つまり、${ }_{2015}\mathrm{C}_{m}$が偶数か否かは末尾に乗じられる$\dfrac{2016-m}{m}$の偶奇による。

 

そこで $m=2N_1$($N_1$は正の整数)と置いて$$\dfrac{2016-m}{m}=\dfrac{1008-N_1}{N_1}$$の偶奇を調べる。ここで$\dfrac{1008-N_1}{N_1}$が偶数になるためには、さらに$N_1$が偶数であることが必要であるから、$N_1=2N_2$($N_2$は正の整数)と置いて、$$\dfrac{1008-N_1}{N_1}=\dfrac{504-N_2}{N_2}$$の偶奇を調べればよい。これが偶数になるためにはさらに$N_2$が偶数でなければならず、以下同様に$N_2=2N_3$、$N_3=2N_4$、$N_4=2N_5$($N_3$、$N_4$、$N_5$は正の整数)と順次置き換えると、$$\small \begin{align} \dfrac{504-N_2}{N_2}&=\dfrac{252-N_3}{N_3} \\ &=\dfrac{126-N_4}{N_4} \\ &=\dfrac{63-N_5}{N_5} \end{align}$$となる。$N_5=1$ のとき、これは偶数となるから、$\dfrac{2016-m}{m}$が初めて偶数となるのは$$m=2^5 \cdot 1=32$$のときである。

 

正の整数 $k \leqq 31$ について$\dfrac{2016-k}{k}$はすべて奇数であるから、${}_{2015}\mathrm{C}_m$が偶数となる最小の$m$は$$m=\color{red}{32}$$である。


(コメント)

某予備校の解答速報には「二進法で着想できないと解答困難」などと頓珍漢なことが書いてあったりしますが、${}_{2015}\mathrm{C}_m$の偶奇がどのように決まるのかを小さい$m$で調べれば容易に方針が立てられます。本問は言ってみれば「差の付く易問」という印象の問題です。

 

勿論、二進法による着眼点も(実際の試験場ではあまり役に立たなさそうですが)数学的には面白いと思います。結局のところ、本問は正の整数 $m$ と $2016-m$ について素因数$2$の個数を比較するだけの問題です。$2016$を二進法で表記すると$11111100000_{(2)}$となるのですが、この意味が分かりますか?

 

例えば、十進法(じっしんほう)の場合を考えてみましょう。$11111100000_{(10)}$は$10$で何回割り切れますか、と聞かれたら$0$の個数を数えれば良いので「$5$回」と即答できます。$11111100000_{(2)}$の場合も同様で、これは$2$で$5$回割り切れます。つまり$2016$を素因数分解したときに得られる$2$の冪(べき)は$2^5$となるのです。

 

要は、$2^5 \cdot 63-m$ の素因数$2$の個数が $m$ の素因数$2$の個数を初めて上回るのはいつか、というのが本問の核心部分です。試験場では実験しながらこれに気が付けるのが理想で、二進数展開が発想できなくても全く解答できないということはありません。そういう意味で、本問は柔軟な思考力を評価する良問と言えないこともないでしょう。

 

東京大学では二項係数に関する問題が定期的に出題されており、今後2, 3年のうちにまた二項係数絡みの整数問題が出題されることが予想されます。東大ではこの問題の他にも、最近だと2009年と1999年に二項係数に関する出題があります。併せて対策しておきましょう。

 

もし余力があれば、${}_{2015}\mathrm{C}_n$が奇数となるような$32$以上の整数$n$を探してみるのも面白いかもしれません。本問の結果を踏まえれば${}_{2016}\mathrm{C}_k$が奇数となるような最小の正の整数$k$も簡単に求めることができますね。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です