流れる空の中で数学を。

ある数学人間の見た世界の記録。数学は趣味でやってます。そろそろ整数論を中心に数学の専門書を読んでみたい。

【ダイジェスト版】 2015東大理系 数学 第5問の解法 【2進法】

前回の記事……なんか長いっ!

 1つ前の記事で、2015東大理系数学第5問を2進法を使ってガンガン解いた。

sky-time-math.hatenablog.jp

  ただ、この記事はたくさん寄り道していて、問題を解きたいだけの人には、余計な情報*1が多い。そんなわけで、なるべく最短ルートで解けるように書き直してみた。

表記法の約束

解法に入る前に、2進法の表記について約束事をしておく。
前回の記事で、11111011111と数字が続き過ぎて見づらかったのを反省した。
では、約束事。

「2進法で同じ数字xk回続くときは、指数を使ってx^kと表す」

例えば、111110111111^5 0 1^5のように表す。
計算しやすさ優先で、1^6=1^5 1みたいに書いたりもするけど、意味は同じ。
最後に、指数が0のときは、その桁が存在しないことにする*2

なお、この表記法を他の人が使ってるかどうかは良く知らないし、面倒なので調べない。これは、「少なくともこのブログ内で使っている表記法」だ。

できるだけ最短ルートな解法

2016を2進法で表すと、1^6 0^5となる*3

m \lt 2^5の場合、
 mを2進法で表すと、その下k+1桁が1 0^kとなるような自然数k \lt 5が明らかに存在する*4。また、2015-m+12進法で表したときの下k+1桁は、
  0^{k+1} - 1 0^k =1 0^k
となるので、mのものと一致する。
 従って、任意の自然数m (\lt 2^5)に対して、2015-m+1mの素因数2の個数は等しい。また、
 {}_{2015} C_m= \frac{2015 \cdots(2015-m+1)}{m!}
    = \frac{2015-m+1}{m} \cdot \frac{2015-m+2}{m-1} \cdots \frac{2015}{1}
と表せるので、m \lt 2^5のときは、{}_{2015} C_mは奇数。


m=2^5の場合、
2015-m+1を2進法で表すと、
 1^5 0 1^5 - 1 0^5 +1 = 1^5 1 0^5 -1 0^5 =1^5 0^6
なので、 2015-m+126回まで割り切れる。従って、\frac{2015-2^5+1}{2^5}は偶数。
ここで①の結果より、{}_{2015} C_{2^5-1}は奇数なので、
 {}_{2015} C_{2^5}={}_{2015} C_{2^5-1} \frac{2015-2^5+1}{2^5}
は偶数となる。

よって、{}_{2015} C_mが偶数となる最小の自然数m2^5

以上!終わり!

*1:一般化ができるくらいには情報盛りだくさんで、これはこれで面白いと思うけど。{}_{31} C_mの偶奇と{}_{2015} C_mの偶奇が一致する話とかは、結構お気に入り。

*2:例えば、1^3 0^0 =1^3 =111

*3:今年はまだギリギリ2016年だから、覚えておくと豆知識として使えるかも。

*4:0自然数とする。