2015年の東京大学理系の整数問題です。
東大というと、かなり難しい問題を出すイメージがありますが、本問は工夫次第で簡単に解くことができます。
手がつけられない場合は、解答を見る前にワンポイントをチェックしてみてください。
問題
$m$ を $2015$ 以下の正の整数とする. $_{2015}C_m$ が偶数となる最小の $m$ を求めよ.
2015年東京大学理系より
解答
まず、コンビネーションの定義より、
$$_{2015}C_m=\frac{2015}{1}\cdot\frac{2015-1}{2}\dots\frac{2015-m+1}{m}$$
となる。
$m$ を $1$ から順に大きくしていくとき、はじめて $_{2015}C_m$ が偶数になるのは、「$2015-m+1=2016-m$ の持つ $2$ の因数の数が、$m$ の持つ $2$ の因数の数より、はじめて大きくなるとき(*)」である。
$m$ と $2016-m$ の偶奇は同じなので、$m$ が偶数の場合のみを考えればよい。
ここから、(*)を満たす $m$ を、$m$ の持つ $2$ の因数の数による場合分けによって求める。
$m\equiv 2\mod 4$ のとき、$2016-m\equiv 2\mod 4$ より不適。
$m\equiv 4\mod 8$ のとき、$2016-m\equiv 4\mod 8$ より不適。
$m\equiv 8\mod 16$ のとき、$2016-m\equiv 8\mod 16$ より不適。
$m\equiv 16\mod 32$ のとき、$2016-m\equiv 16\mod 32$ より不適。
$m\equiv 32\mod 64$ のとき、$2016-m\equiv 0\mod 64$。
よって、求める最小の $m$ は $m\equiv 32\mod 64$ を満たす。
したがって、求める値は $32$ である。
ワンポイント
押さえておきたいポイントは、コンビネーションの定義です。
また、$2$ の因数の数による場合分けも少し工夫が必要です。例えば、$m\equiv 2\mod 4$ は、「$2$ の倍数であるが $4$ の倍数ではない数」を表します。
