暇だったから^[要出典]今年の東大の入試問題数学の問題に目を通してみた。問題文はこのへんやこのへんで参照できるようだ。

ツイッターでの評判を見る感じ、第5問と第6問が話題になっていて、第5問は整数問題、第6問は（大学の）解析学で出てくる概念に関係あるみたいな感じだった。第5問のが問題文が短い（問題文が長いと読むのが面倒くさい）のでとりあえず第5問を解いてみる。

\(\def\Integer{\mathbf{Z}}\)問題文は短いので以下に引用しておく。

第5問

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

オレオレ解法

本題に入る前に、記号について。高校では \({}_{n}\mathrm{C}_m\) を組み合わせ記号みたいな感じで習うが、大学ではアルファベットのシーなんて使わずに二項係数の記号を使う。なのでこの記事でもそうする。一応式で書いておくと、\[
{}_{n}\mathrm{C}_m=\binom{n}{m}=\frac{n!}{m!(n-m)!}
\] である。

二項係数にはいろいろ漸化式とかの公式とかがあるが、基本となるのは二項展開、つまり\[
(a+b)^n=\sum_{m=0}^n \binom{n}{m}a^{n-m}b^m
\]とか\[
(1+x)^n=\sum_{m=0}^n \binom{n}{m}x^m
\]である。

本題だが、二項展開を使って考えてみよう。整数 \(m\) に対して \(\binom{2015}{m}\) が偶数かどうかというのは、多項式 \((1+x)^{2015}\) の \(m\) 次の係数を mod 2 で見たとき（つまり、 \(\Integer/2\Integer\) の元として見たとき）に0かどうかということである。

じゃあ \((1+x)^{2015}\) の \(m\) 次の係数はどうやって計算するの？ということになるが、ここは直接展開する。2015乗すると言っても、\(2015-1\) 回かけ算をする必要はなく、2015の2進展開を使うと割と簡単に計算できる。

2015の2進展開は\begin{align*}
2015&=1\cdot2^{10}+1\cdot2^9+1\cdot2^8+1\cdot2^7+1\cdot2^6 \\
&\qquad+0\cdot2^5+1\cdot2^4+1\cdot2^3+1\cdot2^2+1\cdot2^1+1\cdot2^0 \\
&=((((((((1\cdot2+1)\cdot2+1)\cdot2+1)\cdot2+0)\cdot2+1)\cdot2+1)\cdot2+1)\cdot2+1)\cdot2+1 \\
&=[11111011111]_{\text{2進}}
\end{align*}である。

この2進展開をどう使うかというと、以下のように指数法則を使う。\begin{align*}
(1+x)^{2015}
&=(1+x)^{((((((((1\cdot2+1)\cdot2+1)\cdot2+1)\cdot2+0)\cdot2+1)\cdot2+1)\cdot2+1)\cdot2+1)\cdot\color{blue}{2}+1} \\
&=((1+x)^\color{blue}{2})^{(((((((1\cdot2+1)\cdot2+1)\cdot2+1)\cdot2+0)\cdot2+1)\cdot2+1)\cdot2+1)\cdot2+1}\cdot(1+x)
\end{align*}
ここで、係数を \(\Integer/2\Integer\) で考えているので、 \((1+x)^2=1+x^2\) となることに注意すると、
\begin{align*}
\cdots&=(\color{red}{1+x^2})^{((((((1\cdot2+1)\cdot2+1)\cdot2+1)\cdot2+0)\cdot2+1)\cdot2+1)\cdot\color{blue}{2}+1}\cdot(1+x) \\
&=((1+x^2)^\color{blue}{2})^{(((((1\cdot2+1)\cdot2+1)\cdot2+1)\cdot2+0)\cdot2+1)\cdot2+1}\cdot(1+x^2)(1+x) \\
&=(\color{red}{1+x^4})^{(((((1\cdot2+1)\cdot2+1)\cdot2+1)\cdot2+0)\cdot2+1)\cdot\color{blue}{2}+1}\cdot(1+x^2)(1+x) \\
&=((1+x^4)^\color{blue}{2})^{((((1\cdot2+1)\cdot2+1)\cdot2+1)\cdot2+0)\cdot2+1}\cdot(1+x^4)(1+x^2)(1+x) \\
&=(\color{red}{1+x^8})^{((((1\cdot2+1)\cdot2+1)\cdot2+1)\cdot2+0)\cdot2+1}\cdot(1+x^4)(1+x^2)(1+x) \\
&=\cdots\\
&=(1+x^{1024})(1+x^{512})(1+x^{256})(1+x^{128})(1+x^{64})(1+x^{16})(1+x^8)(1+x^4)(1+x^2)(1+x)
\end{align*}を得る。

我々は係数が0になる最小の次数に興味があるので、次数が低い部分を展開してみよう。
\begin{align*}
(1+x^2)(1+x)&=1+x+x^2+x^3, \\
(1+x^4)(1+x^2)(1+x)&=1+x+x^2+x^3+x^4+x^5+x^6+x^7, \\
&\vdots \\
(1+x^{16})(1+x^8)(1+x^4)(1+x^2)(1+x)&=1+x+x^2+\dots+x^{30}+x^{31}.
\end{align*}
一方、次数が大きい部分は展開すると\[
(1+x^{1024})(1+x^{512})(1+x^{256})(1+x^{128})(1+x^{64})=1+x^{64}+x^{128}+\cdots+x^{1984}
\]となる。よって、 \((1+x)^{2015}\) はこれらの積で、\begin{align*}
(1+x)^{2015}&=(1+x+x^2+\dots+x^{30}+x^{31})(1+\text{(64次以上の項)}) \\
&=1+x+x^2+\dots+x^{30}+x^{31}+\text{(64次以上の項)}
\end{align*}と書ける。

これを見ると、係数が 0 になる最小の次数は32である。よって、この問題の答えは \(m=32\) である。

この問題には2015というマジックナンバーが出てきたが、この解法の考え方でいくと、2進展開さえできれば2015じゃなくても解ける。

使った知識について

テクニックという言い方はアレだが、多項式の係数を \(\Integer/2\Integer\) で見る（mod 2 で見る）のと、べき乗を指数の2進展開で計算するのを使った。

今の高校生って授業で合同式を習うんだっけ？みたいな疑問があるが、まあ東大を目指す人なら知っていてもおかしくないだろう。多分。どうだろう。

おまけ

コンピューターを使って実際に計算してみると以下のようになる。

$ ghci
GHCi, version 7.8.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> let binom n m = product [1..n] `div` (product [1..m] * product [1..n-m])
Prelude> binom 4 2
6
Prelude> binom 5 2
10
Prelude> minimum [m | m <- [0..2015], binom 2015 m `rem` 2 == 0]
32
Prelude> binom 2015 32
16186954748025166046263663997642430244064006144786443959701793710268550
Prelude> binom 2015 31
261079915290728484617155870929716616839742034593329741285512801778525
Prelude> [binom 2015 m | m <- [0..32]]
[1,2015,2029105,1361529455,684849315865,275446394840903,92274542271702505,26482793631978618935,6647181201626633352685,1482321407962739237648755,297353674437325491072340253,54199465204257964509094746115,9051310689111080073018822601205,1394598100791499491250515513093355,199427528413184427248823718372349765,26603632290318802594993084030871458651,3325454036289850324374135503858932331375,391034271679024164613170404247882690024625,43404804156371682272061914871514978592733375,4562073363172328920910928631495548013141502625,455294921644598426306910677423255691711521961975,43253017556236850499156514355209290712594586387625,3920296227597103631605367710194878440041527511678375,339702190504392501643021645496451857869685405685869625,28195281811864577636370796576205504203183888671927178875,2245472243496894962960570239329006354741564893832280525605,171864990944570037549674414471720101766758236104855317152075,12660720999583326099492681866083380830151190059724341696869525,898911190970416153063980412491920038940734494240428260477736275,61590915050283341246142382055911900599146187588128653571353861325,4077318576328757190494625692101367819663477618334116866423625619715,261079915290728484617155870929716616839742034593329741285512801778525,16186954748025166046263663997642430244064006144786443959701793710268550]
Prelude> 

Tweet