₂₀₁₅C_mが偶数になる最小のm ［2015 東京大・理］

イズミの解答への道

解答

　いま、

である（ただし、 1 ≦ k ≦ m ）。m を1から順に大きくしていくとき、分母に含まれる素因数 2 の数より分子に含まれる素因数 2 の数が初めて多くなる m が求める m である。

　以下、 m が奇数となる項は省いて考えても問題に影響はない。そこで以下のように、 m と 2016 – m が2で何回割れるかを表わした表を作成する。図の * は 2 で割り切れる回数を表している。すると、

となり、m = 30 までは m と 2016 – m の2で割り切れる回数は同じで打ち消しあうため、₂₀₁₅C_m の値は奇数となるが、 m = 32 のとき、32 は 2 で 5 回しか割り切れないのに対し、 2016 – 32 = 1984 は 2 で 6 回割り切れる。
　よって、 m = 32 のとき初めて分母に含まれる素因数 2 の数より分子に含まれる素因数 2 の数が初めて多くなるので、求める答えは 32 である。

解説

“力づく”から“エレガント”へ

　上の解答は、力づくの解答ではあるが、試験場ではまずは答案を作ることが大事であり、上記の解答でも丸はもらえるだろう。
　しかし、今回はたまたま32という比較的早い段階で答えが出たからよいが、常にこんなに簡単に答えが出るとは限らない。
　そこで、この解答で見えてきたルールをもとに、この問題をどのように解けば良いのかを考えてみよう。

解答1

（後日書きます。）

解答2

　「 n が k で何回割り切れるか」という問題は中学校で学ぶ素因数分解がベースになっているが、この素因数分解には k 進法の考え方が潜んでいる。（ k 進数に変換するときの計算は、kで割り続けることだったはずだ！）
　例として簡単な例を考えてみると、「2016は2で何回割り切れるか」という問題は、
　　2016₍₁₀₎ = 11111100000₍₂₎
と2進法に直せるが、見方を変えれば、下から 5 桁に 0 が並ぶことが、 2 で 5 回割れることを表しているといえる。

　ここからが本題である。2進法表記の m と 2016 – m を考えたときに、初めて下から並ぶ 0 の数が m より 2015 – m が大きくなる m がいくつかを考えればよい。

　例えば、
　　m = 100₍₂₎
の場合、
　　2016 – m = 11111011100₍₂₎
となり、下からの0の数はどちらも2つとなり、該当しない。

　下からの0の数が重要なので、2進数表記で下の桁が1になるような数、すなわち
　　m = **1₍₂₎
のような数は省いてよい（これは、解答で「奇数は飛ばして良い」としたのと同じこと）。2進法表記の m の下の桁が 0 になるような数を、小さい方から考えていけばよい。また、
　　2016₍₁₀₎ = 11111100000₍₂₎
としたから 5 個 0 が並ぶ数であることから、2進法で下4桁が0である数までは、2進法表記の m と 2016 – m の末尾に並ぶ0の数は等しくなるのでこれも無視してよい（ここがミソ。解答では32までの偶数をすべて確認したが、このやり方であれば、32以下の数はいちいち確認しなくても良いということがこのことから示される）。

　これらのことから、末尾に並ぶ0の数に差異ができるのは、
　　m = 100000₍₂₎
のときであり、実際に、
　　2016 – m = 11111000000₍₂₎
となり、 m の末尾の 0 が 5個、 2016 – m の末尾の 0 が 6 個となるため、求める m であることが分かる。
　最後に、
　　m = 100000₍₂₎
を10進法表記に戻して、求める m = 2⁵ = 32 である。