東京大学 理系 2015年度 第5問 解説
問題編
問題
m を 2015 以下の正の整数とする。 ${}_{2015} \mathrm{C} _m$ が偶数となる最小の m を求めよ。
考え方
でました。2015年度で一番の「何をどうしたらいいのかよくわからない問題」です。
こういう場合は、とりあえず実験してみましょう。$m=1$ の場合から順番に書き出してみます。
${}_{2015} \mathrm{C} _1=2015$ で奇数ですね。
${}_{2015} \mathrm{C} _2 = 2015×2014/2=2015×1007$ で奇数。
${}_{2015} \mathrm{C} _3$は、\[2015×2014×2013/(3×2)=2015×1007×671\]で、やっぱり奇数。
当たり前ですが、奇数ですね。こんなところで偶数になってたら問題にならないですからね。分子に偶数が現れても、分母にある偶数と打ち消し合って、結局奇数になってしまいます。
$\displaystyle{}_{2015} \mathrm{C} _m=\frac{2015!}{m!(2015-m)!}$ です。分母分子を $(2015-m)!$ で割ると、分子は、 $2015$ から $(2015-m+1)$ までの $m$ 個の積、分母は $1$ から $m$ までの $m$ 個の積です。
つまり、${}_{2015} \mathrm{C} _m$ と ${}_{2015} \mathrm{C} _{m-1}$ の違いは、分子に $2016-m$ があることと分母に $m$ があることです。上のように順番に ${}_{2015} \mathrm{C} _m$ を見ていった場合、これがはじめて偶数になるのは、 $(2016-m)$ を $2$ で割れる回数が $m$ を $2$ で割れる回数をはじめて上回る時です。
$2$ で割れる回数に着目すればいいので、 $2016=2^5\cdot 63$ 、 $m=2^a\cdot b$ と書いてみます（b は奇数）。すると、 $(2016-m)=2^a(2^{5-a} \cdot 63 - b)$ となります。分母の $m=2^a\cdot b$ は2で a 回割れるので、分子は $a+1$ 回以上割れないといけません。つまり、このカッコの中が偶数になるしかありません。こうなると、もう答えが見えてきます。
ここまでのことをふまえて、解答に仕上げていきます。
解答編
問題
m を 2015 以下の正の整数とする。 ${}_{2015} \mathrm{C} _m$ が偶数となる最小の m を求めよ。
解答
\begin{eqnarray} {}_{2015} \mathrm{C} _m &=& \frac{2015!}{m!(2015-m)!} \\[5pt] &=& \prod_{k=1}^m \frac{2016-k}{k} \end{eqnarray}である。ここで、 $k \lt 32$ とし、 $k=2^a\cdot b$ と書く（b は奇数）。このとき $a\lt 5$ となる。
\begin{eqnarray}
\frac{2016-k}{k}
&=& \frac{2^a(2^{5-a}\cdot 63 - b)}{ 2^a\cdot b } \\[5pt]
&=& \frac{2^{5-a}\cdot 63 - b}{ b }
\end{eqnarray}
ここで、 $2^{5-a}$ は偶数なので、分子は奇数。よって、 $m \lt 32$ のときは、 ${}_{2015} \mathrm{C} _m$ は、奇数/奇数の積なので、偶数になることはない。
$m=32$ とする。このとき
\begin{eqnarray}
\frac{2016-32}{32}
&=& \frac{2^5(63 - 1)}{ 2^5 } =62
\end{eqnarray}
なので、 ${}_{2015} \mathrm{C} _m$ は偶数になる。
よって、求める値は $32$ である。
（解答終）
解説
$2016=2^5\cdot 63$ 、 $m=2^a\cdot b$ と書いたとき（b は奇数）、\[(2016-m)=2^a(2^{5-a} \cdot 63 - b)\]となります。そのため、これを分母の $m=2^a\cdot b$ で割った答えが偶数になるには、このカッコの中が偶数になるしかありません。そうすると、a は5以上でないとダメで、b が一番小さいときは1なので、答えは32とわかります。このことから、上の解答では、31以下では無理ということ、32では条件をみたすということを示し、32が求める答えである、としています。
$2016-k=2^{11}-2^5-k$ なので、
\begin{eqnarray}
{}_{2015} \mathrm{C} _m
&=&
\prod_{k=1}^m \frac{2^{11}-2^5-k}{k}
\end{eqnarray}と書くことができます。
この形をよく見れば、 $k\lt 2^5$ のときは、分母分子で素因数2の個数が一緒で、 $k= 2^5$ のときにはじめて分子が $2^6$ で割り切れることがわかります。つまり、この問題は2015にちなんだ問題と見せかけて、実は2016にちなんだ問題であり、 $2016=2^{11}-2^5$ と書けることがかなり効いていたんですね。
