二項係数C(2015, m)が偶数になる最小のm / 2015 東京大学・理系第5問

問題
解答・解説

問題

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

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

解答・解説

${}_{2015}\mathrm{C}_m$ を展開（？）すると分数式になります。
その分母，分子が 2 で何回割りきれるか調べて，分子の方が割りきれる回数が多くなるのはいつなのか調べるのが自然でしょう。

\begin{align*}
{}_{2015}\mathrm{C}_m =\frac{2015!}{m!\, (2015-m)!}=\frac{2015\cdot 2014\cdots (2016-m)}{m(m-1)\cdots 1}
\end{align*}

分母，分子が 2 で割りきれる回数をそれぞれ $f(m)$ , $g(m)$ とおきます。
$g(m)>f(m)$ となる最小の $m$ が答えです。

分母について

分母は階乗なので簡単です。

$f(m)=\sum_{k\geqq 1} \left[ \frac{m}{2^k}\right]=\left[\frac{m}{2^1}\right]+\left[\frac{m}{2^2}\right]+\cdots\mbox{　……(1)}$

実例をいくつかあげておきます。

\begin{align*}
f(2)&=\left[\frac{2}{2}\right]=1,\, f(3)=\left[\frac{3}{2}\right]=1,\, \\
f(4)&=\left[\frac{4}{2}\right]+\left[\frac{4}{4}\right]=2+1=3,\, \\
f(5) &=\left[\frac{5}{2}\right]+\left[\frac{5}{4}\right]=2+1=3,\,\\
f(8)&=\left[\frac{8}{2}\right]+\left[\frac{8}{4}\right]+\left[\frac{8}{8}\right]=4+2+1=7
\end{align*}

一般に $f(2^m)=2^m-1$ です。また， $f(m)$ と $f(m-1)$ の関係は次のようになります。