【問題解説】東大一行問題をドキドキしながら解いてみた。

以前のブログで、数学に興味を持ち始めた人へ手始めに考えてもらう問題としてとある東大の問題を紹介したが、最近数学好きだという同僚にその問題の話をしていたら

「あ、それ東大の一行問題ですね」

といわれて、恥ずかしながら初めてそういったジャンルを知った。確かにときどきこんなシンプルな問題が問われていることは知っていたが、そのような名称がついていたことを知らなかった。で、そのことを正直に話したら、

「他にも

『${}_{2015} \mathrm{C}_{m}$が偶数となるような最小の$ m $を求めよ』

とかありますよ」

と教えてもらった。これまた毎年東大の問題を解いていたわけでもなかったので知らなかった。

「解けますか(笑)」

なんてことを言われたから、久々に入試気分でドキドキしながらチャレンジしてみた。無事解けたからメンツは保たれたし（メンツってなんだっけ？）、いい問題な気がしたので、今回はここでその解答を紹介したい。何を今更と言う方にはゴメンナサイ。

ここから解説。

とりあえず$ m $に$1、2、3$と代入してみて、（こんな最初の方の数はどうせ奇数だろうから）どんな感じで奇数になるのか様子を見るかなとも思ったけど、解いてるとこ見られてたので、具体化したときになんの傾向も掴めなかったら恥ずかしくてその策は諦めた。この実験とか観察と称していくつか数値を代入してみて何らかのものを予測するという態度はよくあるもので、けしてそれを否定するものではないが、これは見方を変えれば策がないときの博打策ともいえなくもない。なんらかの姿よ、見えてこいと期待してその様子をうかがうのである。

${}_{2015} \mathrm{C}_{m}$がでてくること、$ m $が自然数であること、求めるものが偶数になるということから、まずこういったことに対して何を知ってるっけと考えてみた。

${}_{2015} \mathrm{C}_{m}$からは、コンビネーションの定義とその定性的意味が組み合わせであること、計算テクの種として2項定理あたり。

$ m $が自然数であること、求めるものが偶数になるということから、数列であること（変数がでてきて、それが例えば実数であれば関数としてみれるかとか、自然数だったら数列としてみれるかと考えてみる）、整数問題としてみれること。

こういったことがまず思い当たった。で、これらのうちどの道具から使っていくかだけど、${}_{2015} \mathrm{C}_{m}$を$2015$個のものから$ m $個とる組み合わせの数、なんていえたところで何のヒントにもならないし、2項定理とみなしても定理に現れるシグマをいい感じに対処する術がすぐにわからなかったので、まずは定義式で表すしかないかなと思った。つまり

${}_{2015} \mathrm{C}_{m}=\dfrac{2015 \cdot 2014 \cdots (2015-m+1)}{m \cdot ( m -1 ) \cdot ( m -2 ) \cdots 3 \cdot 2 \cdot 1 }$

という形だ（厳密には定義から約分しているが）。

で、これが偶数となる最小の$ m $を考えるわけだが、これをすぐに整数問題と捉えて解けるかと問われたならば、式が少し複雑で整数問題ならではのアプローチ（離散量であることや約数・剰余類を用いた方法）がこのままだと取りづらい。なので、数列の観点から切り崩せないか考えてみる。

$a_{m}={}_{2015} \mathrm{C}_{m}$

として考えてみるということだ。

数列としてみるとき、その数列の特徴を表す方法は大きく分けて2つある。一般項の形にすることと漸化式の形にすることだ。この2つは、前者は数列をその絶対的な位置から表したもので、後者は相対的に表したものとみることができる。よく学校なんかでは漸化式から一般項を求めるということばかりするせいかこういった見方に疎くなりがちだが、この2つは観点の異なる数列の表現方法である。有名なフィボナッチ数列を考えるとわかりやすくて、一般項はあまりスッキリしたものではないが漸化式（$a_{n+2}=a_{n+1}+a_{n}$）はその特徴がよく見えている。

さて、この問題において、$a_{m}={}_{2015} \mathrm{C}_{m}$として一般項を表してみましたとしたところで何も得られそうにないので、漸化式の形にすることを考えてみる。

単（ひとえ）に漸化式と言っても、何項の間で立式できるだろうか。例えば、教科書でよくみるような易しい問題は二項間だし、先の例にだしたフィボナッチ数列は三項間で定義されている。ここで単純な方から考えてみたい。我々が一般項と漸化式の形を直接往来できるのは二項間漸化式のときで、二項間以外の場合は、一旦二項間の形で表現しなければ一般項にたどり着かないはずだ。ということで、まず二項間で表現できないか考える。$a_{n+1}$を$a_{n}$の式で表せればいいので、$a_{n+1}$から$a_{n}$を目指して式変形してみる。

$a_{n+1}={}_{2015} \mathrm{C}_{n+1}$

$=\dfrac{2015 \cdot 2014 \cdots (2015-(n+1)+1)}{n+1 \cdot ( (n+1) -1 ) \cdot ( (n+1) -2 ) \cdots 3 \cdot 2 \cdot 1 }$

$= \dfrac{ 2015-(n+1)+1 }{ n+1 } \cdot \dfrac{2015 \cdot 2014 \cdots (2015-n+1)}{n \cdot ( n -1 ) \cdot ( n -2 ) \cdots 3 \cdot 2 \cdot 1 } $

$= \dfrac{ 2015-n }{ n+1 } \cdot {}_{2015} \mathrm{C}_{n} $

と意外に簡単に漸化式が完成。この漸化式と問題文を見比べてみると、なるほど$\frac{ 2015-n }{ n+1 }$が$n$をカウントアップしていくと途中までは奇数で、あるところで偶数になるということがわかる。

ということで

$\dfrac{ 2015-n }{ n+1 }＝偶数$

となる場合を考える。この式で偶数になるような最小の$n$は何かということなので、この偶数という日本語を$2k$と翻訳して計算ができるようにしておく。

$\dfrac{ 2015-n }{ n+1 }＝2k$

文字が2つに式が1つなので不定方程式とも捉えられるが、登場人物が整数（自然数）なので、整数問題というアプローチの方が条件がきつい分向いている。で、整数問題と捉えると、整数の性質（離散量であることや約数・剰余類を用いた方法）が使える。不等式の条件などがあれば離散量であることは活きてくるが、ここではあまり有効ではない。

すると、約数か剰余類（割り算のあまり）が残るアプローチとなる。これらの違いは、割り切れる値と捉えて考えるか、割り切れない値としてそのあまりの周期性などに着目して考えるかである。割り切れるか・割り切れないかを考えるということは、ざっくりいえば積の形（因数分解）で表現できるかどうかということだ。

え。何を表現するの？と思った人。もちろん整数を表現するのである。$\frac{ 2015-n }{ n+1 }は2k$で左辺が分数の形をしているものの、登場人物すべてが整数だ。

ここで文字の場合、整数と命名されただけに過ぎない。$ n $とか$ k $に「お前、整数な」と言っただけだ。文字表現の整数は言われたことには従うが、自ずからその特性を表現することは難しい。それに比べ、$2015$は生粋の整数である。こいつに着目する。分母をはらって、$2015＝$の形にしてみる。

$2015=2k(n+1)+n$

この右辺を因数分解したい。といわれてもできないよと言われそうだが、定数項ならば左辺に追いやればいいのでその程度の調整はありだ。右辺のふたつの項に共通因数があればいいわけで、ひとつめが$2k$と$n＋1$でふたつめが$n$となっている。じゃふたつめを$n+1$にして、余計に足した1は両辺に1足したことにして、$2015$を$2016$にすればOKだ。

$2016=2k(n+1)+(n+1)=(2k+1)(n+1)$

となって、無事因数分解できた。これで約数を考えることができる。

$ 2016=2^{5} \cdot 3^{2} \cdot 7 $

となる。この5個の2と2個の3と1個の7を2つ数字のかけ算で表すわけだが、この5個の2は偶数なので$2k+1$の側へはいけない。2個の3と1個の7はどちらの側に考えてもOKだ。で、問題はこの$n$が最も小さいときを求めているので、どちらでもいい2個の3と1個の7は$2k+1$側の数字と考える。つまり、

$2016= 3^{2} \cdot 7 \cdot 2^{5} $

として、$3^{2} \cdot 7 =2k+1$、$2^{5}=n+1$とするわけだ。これより$n=31$となる。ゆえに

$a_{32}= (偶数) \cdot {}_{2015} \mathrm{C}_{31} $

と表現できて、$a_{32}$が最小の偶数になることがわかる。つまり答えは$m=32$である。

解説おわり。

考えているふりして解けない言い訳を考えるようなことにならずに済んでよかった。ふぅ。でも楽しかったので、そんな感動を読んでるあなたにお裾分けできてたら光栄だ。