東京大学 2015年度 前期日程 第2次学力試験理系数学 第5問

$$2016=32\cdot 63=2^5\cdot 63$$ である。

$1\leqq j\leqq 31$ とする。$j$ に含まれる因数 $2$ の個数を $r$ とすると、$j<32$ だから $0\leqq r\leqq 4$ であり $j=2^{r}s$ と書ける。ただし $s$ は奇数である。このとき $$2016-j=2^r(\frac{2016}{2^r}-s)$$ である。$r\leqq 4$ より $2016\mathrm{/}{2}^r$ は偶数であり、$s$ は奇数なので $\frac{2016}{2^r}-s$ は奇数である。したがって、$2016-j$ に含まれる因数 $2$ の個数も $r$ である。

$1\leqq m\leqq 31$ のとき$${}_{2015}{\mathrm{C}}_m=\frac{2015\cdot 2014\cdots (2016-m)}{m!}=\frac{(2016-1)(2016-2)\cdots (2016-m)}{1\cdot 2\cdots m}$$である。上で示したように、各 $j=1,2,\dots ,m$ について、分子の因数 $2016-j$ と分母の因数 $j$ に含まれる因数 $2$ の個数は等しい。したがって分子全体と分母全体に含まれる因数 $2$ の個数も等しく、約分後に因数 $2$ は残らない。ゆえに ${}_{2015}{\mathrm{C}}_m$ は奇数である。

次に $m=32$ を調べる。$j=1,2,\dots ,31$ に対応する部分では、先ほどと同様に因数 $2$ の個数は分子と分母で等しい。残る $j=32$ に対しては $2016-32=1984=2^6\cdot 31$ である。一方、分母側の因数は $32=2^5$ である。したがって $j=32$ の部分で分子側に因数 $2$ が1個多く、全体として ${}_{2015}{\mathrm{C}}_{32}$ は偶数である。

以上より、${}_{2015}{\mathrm{C}}_m$ が偶数となる最小の $m$ は $32$ である。

二項展開の係数を2で割った余りだけ考える。$(1+x{)}^{2^k}$ の中間係数がすべて偶数であることから、指数2015の2進表示を使って $(1+x{)}^{2015}$ を2を法として因数分解する。係数が奇数になる次数を、選べる2の冪の和として判定する。

多項式の係数を2で割った余りで考える。二項係数の対称性とパスカルの関係、または二項展開を繰り返すことにより、正の整数 $k$ について$$(1+x{)}^{2^k}\equiv 1+x^{2^k}(\mathrm{m}\mathrm{o}\mathrm{d}2)$$が成り立つ。

2015の2進表示は$$2015=1024+512+256+128+64+16+8+4+2+1$$であり、$32$ の位だけが欠けている。したがって$$\begin{array}{rl}{\displaystyle (1+x{)}^{2015}\equiv }& {\displaystyle (1+x^{1024})(1+x^{512})(1+x^{256})}\\ {\displaystyle }& {\displaystyle \cdot (1+x^{128})(1+x^{64})(1+x^{16})(1+x^8)}\\ {\displaystyle }& {\displaystyle \cdot (1+x^4)(1+x^2)(1+x)(\mathrm{m}\mathrm{o}\mathrm{d}2)}\end{array}$$である。

右辺を展開すると、各因子から $1$ または $x^{2^j}$ を選ぶ。異なる選び方は2進表示の一意性により異なる次数を与えるので、ある次数 $m$ の係数が奇数であるための必要十分条件は、$m$ の2進表示で1となる桁が、上に並んだ桁だけからなることである。

$1\leqq m\leqq 31$ では使う桁は $1,2,4,8,16$ だけであり、これらの因子はすべて存在する。よって$${}_{2015}{\mathrm{C}}_m\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}2)(1\leqq m\leqq 31)$$である。

一方、$m=32$ の2進表示は $100000$ であり、必要な $x^{32}$ の因子が存在しない。したがって$${}_{2015}{\mathrm{C}}_{32}\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}2)$$である。以上より、偶数となる最小の $m$ は$$32$$である。