流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

「2015東大理系 第5問」を2進法でガンガン解こうぜ!! ~ついでに一般化できたかも?~

Youtubeを散歩してたら……

 なんとなくオシャレ、かつあんまし時間のかからなそうな整数論の問題をYoutubeで見かけた*1

【話題の一行問題】東大数学2015第5問【2015Cmが偶数】 - YouTube

というわけで、久々に更新。
 サクサクのおやつみたいに手軽に楽しめる問題なので、遊びたい人は自分でチャレンジしてみてください。ちょっとした気分転換になると思うよ!

2015東大理系 第5問

 問題は次の通り、

 m2015以下の正の整数とする。 {}_{2015} C_{m}が偶数となる最小の mを求めよ。』

 これを気楽に解いてみた*2
 2進法を使って解いてみたのが、結構気に入ったので公開してみる。そう、2進法でガンガンいってるので、受験生は真似しない方がいいかも*3……
 要は、どこかの数学好きが、少しでも楽しくなればOKというスタンスなのだ。

今回のあらすじ

 ステップ1:m=2^nの場合にm!を調べてみた。これは寄り道。
 ステップ2:2進法を使う解き方の始まり~。そして、怪し過ぎる数を見つける!
 ステップ3: {}_{2015} C_{m}が奇数であり続ける、そのギリギリまで一掃する!
 ステップ4: {}_{2015} C_{m}がついに偶数に!ついでに一般化も?

ステップ1(寄り道): m=2^nのとき、m!2で最大何回割れるか?

 最初にやった実験を紹介してみる。けど、この方針は途中で面倒になって放棄したので、興味ない人や解法だけ知りたい人はステップ2から読んだ方が良いです。
整数問題が苦手な人が、この問題を考える練習くらいにはなってるかも?*4

  {}_{2015} C_{m}=\frac{2015\cdots(2015-m+1)}{m!}

が偶数かどうかを考えたいから、分子分母が2で何回割り切れるかを調べるのが基本方針になる。

 そこで、分母に現れるm2でぴったりn回割り切れるm=2^n (n \in \mathbb{N})と表せる場合から考えてみる。
このとき、 m! = (2^n)! 2で最大何回まで割り切れるか?(素因数2の個数)

これを知りたくなって、冪のリズムに合わせて、

  m! = (2^4)! =1 \times 2 \times (3 \cdot 4) \times (5 \cdot 6 \cdot 7 \cdot 8) \times (9 \cdot 10 \cdot 11 \cdot 12 \cdot 13 \cdot 14 \cdot 15 \cdot 16)

とかテンポ良く書いてみた。

それで、この式をちょっと観察すると、

 (2^n +1) (2^n +2) \cdots (2^{n+1})に含まれる偶数は、 (2^{n-1} +1) (2^{n-1} +2) \cdots (2^{n})に現れる数1つ1つに2をかけたものに一致する」

と気づく。逆に言うと、
 (2^n +1) (2^n +2) \cdots (2^{n+1})に含まれる偶数を全て取り出し、それぞれ2で割ってから、もう一度かけ直すと、 (2^{n-1} +1) (2^{n-1} +2) \cdots (2^{n})にピッタリ一致する*5。」

 この観察結果から、 (2^{n-1} +1) (2^{n-1} +2) \cdots (2^{n})に含まれる素因数2の個数をa_{n}とおいて考えてみる。まず、2^121回だけ割れるからa_{1}=1だ。一般のnのときは、上に書いた観察から、

  a_{n+1}=a_{n}+2^{n}-2^{n-1}
と書けることが明らかなので、少し式変形して、
 a_{n+1}-2^{n}=a_{n}-2^{n-1}=\cdots=a_{1}-2^{0}=0
\iff a_{n}=2^{n-1}
つまり、 (2^n +1) (2^n +2) \cdots (2^{n})2で、最大2^{n-1}回割れる。
よって、

『定理1:  m! = (2^n)! 2で、最大2^{n}-1(=1+2+\cdots+2^{n-1})回割れる。』

と分かる。これを使うと、1から1024=2^{10}までの数を1つずつかけた数は、21023(=2^{10}-1)回割れるとかすぐにわかる*6

ステップ2: 2015を2の冪を使って表してみたくなる。そして、2進法へ……

 分母に現れるm2の冪の場合は、ステップ1で調べた。
次は分子だが、2015は偶数じゃない。けど、2の冪を使う方針を押し通したい。そんな理由で、2進法を使ってみることにした。

すると、驚愕の事実が分かった!

 『驚愕の事実1:  2015は2進法で11111011111_2と表せる』

これは、
 2015=2^{10}+2^9+2^8+2^7+2^6+2^4+2^3+2^2+2^1+2^0
と表せるということなので、あからさまに2^5が怪しい*7
推理小説にしたら、「犯人臭」出し過ぎもいいところじゃないか~
これで、2^5が犯人(正解)だったら、推理小説としては残念なレベル……
初見で感じた「オシャレ感」も3割りくらい引っ込めたい気持ちに*8……
一応結末は、この記事の最後ということで……


 さて、計算結果1を改めて見つめて、桁の小さい方から大きい方へと指でなぞってやる。すると、ちょうど真ん中にある0が「壁になってる感」がある。
そこで少し観察をして、2進法の定義に立ち返りつつ進むことにした。

突然だが、ここで以下の数々を見比べていただきたい。
 11111011111_211111_2
 11111011011_211011_2
 11111010100_210100_2
さて、右と左の数の関係は何か?

 答えは、「右に書いてある数は、左に書いてある数において、中央にある0より右側の数字だけを取り出したもの」でした。言ってみると、右の数は「0の壁のこちら側」の世界である。

なぜ、「0の壁のあちら側*9」を捨てたのか?

答えは、割りとシンプルで、2で割れる回数が等しいからだ。つまり、

x_i =0,1 (i=0,1,2,3,4)とし、x_4 x_3 x_2 x_1 x_00でないとする。
このとき、
X=111110 x_4 x_3 x_2 x_1 x_0
という2進数Xを考えると、X2で割れる最大回数は、x_4 x_3 x_2 x_1 x_0に一致する。」

 このことがすぐわからない時は、10進数の場合を考えるといいかも。
例えば、10進数で11111038400
と数を考えると、
 32741038400=32741000000+38400
なので、327410384003840010で割れる回数は等しい。
と、こんな感じだ。


以上をまとめて、

『定理2:2進法において、x_4 x_3 x_2 x_1 x_00でない自然数とする。このとき、x_N \cdots x_6 0 x_4 x_3 x_2 x_1 x_0*10を2で割り切れる最大回数は、x_4 x_3 x_2 x_1 x_0のものと一致する。

と分かった!

 これを応用すると、2015から2015-2^5+1までの数に含まれる素因数2の個数が知りたいときは、
 2015=11111011111_231=11111_2
 2014=11111011110_230=11110_2

         \cdots

 2015-2^5+1=11111000001_21=1_2

と置き換えて調べればいいと言える。このことから、m \lt 2^5ならば、 {}_{2015} C_{m}=\frac{2015\cdots(2015-m+1)}{m!}の偶奇と、 {}_{31} C_{m}=\frac{31\cdots(31-m+1)}{m!}の偶奇は一致していると分かる。
というわけで、m \lt 2^5の場合は簡単に
調べられるので、ステップ3へGO!

ステップ3:解法(m \lt 2^5のとき、 {}_{2015} C_{m}が奇数であること)

 m \lt 2^5の場合、定理2より、
2015\cdots(2015-m+1)31\cdots(31-m+1)は、2で割り切れる回数が等しい*11
 よって、mが1から31までの{}_{31} C_{m}の偶奇を調べれば、この問題はほとんど解けたようなものと言えるだろう。実際は、{}_{31} C_{m}={}_{31} C_{31-m}なので、mは折り返し地点までの16まで調べれば十分十分!そこで、以下、m\leq16とする。

ここで、312進法で11111_2と表せることにジッと注目した。
mは仮定より、2進法で x_4 x_3 x_2 x_1 x_0と表せる。
後は、11111_2-m+1mが2で割り切れる回数が等しいことを示せば良さそうだ。もうほとんど自明かもしれないけど、一応計算をつけておく。

m2で割れる最大の回数がkの場合、x_0=x_1=\cdots x_{k-1}=0かつx_k=1なので、

 11111_2-m+1

=11111_2-(m-1)

=11111_2-(x_4 \cdots x_{k+1} 1 0 \cdots 0_2 -1_2)

=11111_2-x_4 \cdots x_{k+1} 0 1 \cdots 1_2

 

この計算から、11111_2-m+12進数で表すと、その下k桁は1 0 \cdots 0に一致する。
 従って、11111_2-m+1m2で割り切れる最大の回数は等しい。
これより、31\cdots(31-m+1)2で割り切れる最大の回数はm!と等しいので、

  {}_{31} C_{m}が奇数であることがわかる。

ここまでの話は、そのまま一般化できて、次の定理が成り立つ。

『定理3:自然数n2進法で11\cdots1_21のみで表せるとき、k=0,1,2,\cdots,nに対して、{}_{n} C_{k}は奇数。』

ステップ4:解法( {}_{2015} C_{2^5}が偶数であること)

残すは、m=2^5の場合に、 {}_{2015} C_{m}が偶数になることを示したら終わりだ。これも2進法を使うとかなり楽。

ステップ2で示したように、k \lt 2^5までは2015\cdots(2015-k+1)31\cdots(31-k+1)は、2で割り切れる回数が等しい。
そこで、
 {}_{2015} C_{m}=\frac{2015\cdots(2015-m+1)}{m!}
    =\frac{2015\cdots(2015-m+2)}{(m-1)!} \cdot \frac{m}{2015-m+1}
と分解する。\frac{2015\cdots(2015-m+2)}{(m-1)!}はステップ3の結果より奇数なので、m2015-m+1に含まれる素因数2の個数を比較すれば終わりである*12

仮定より、m=2^52でちょうど5回割れる。次に、
 2015-m+1

=11111011111_2-100000_2+1_2

=11111100000_2-100000_2

=11111000000_2
となるので、2015-m+126回割り切れる。
従って、{}_{2015} C_{2^5}は2で1回割り切れるので偶数。

ステップ3の結果と合わせて、 {}_{2015} C_{m}が偶数となる最小の m2^5であることが示せた!
というわけで、なんと……最初から最後まで2進法のターンでした!

ステップ4での結果も、ステップ3と同様にそのまま一般化できる気がしている*13。つまり、

『予想1:任意の自然数nが、2進法で x_N \cdots x_{k+2} x_{k+1} 0 1\cdots 1_2と表せるとする*14*15{}_{n} C_{m}が偶数となる最少のm2^{k-1}。』

正しかったら、これで完全な一般化になっているはず!
合ってたら超嬉しい!やほーーい!

 

*1:自分で解きたくなったから、途中までしか見てません。もし解法かぶりすぎてたら、動画をupした方、ごめんなさい。

*2:あくまで、数学は趣味と気分転換を兼ねてやってます。解けなくても、あんまり気にしないスタイル。

*3:私のときは、高校で2進法習った覚えがない

*4:と言いつつも、ステップ1の半分くらいは、自分用のメモor思考のスナップショットのつもり。

*5:それはもう、シャキーンと音が聞こえそうなくらいに、ピッタリと一致している。

*6:なんも知らない人の前でやると、「計算はえ~」という感嘆、または宇宙人を見たときのような驚き、どっちかの反応をされるかもしれません。なお、むやみに人を驚かすのは推奨してませんよ~

*7:単に怪しいとかいうレベルじゃなくて、「怪しい」。そう、「怪しい」のだ。

*8:それでも、残り7割残してるのは、111110111110に対して対称的だから。やっぱり、それなりにオシャレなのかもしれない。

*9:20150の壁の左側の数のこと

*10:Nはある自然数

*11:含まれる素因数2の個数が等しいと、すっきり言ってもいい。

*12:ここで、\frac{m}{2015-m+1}自然数ではないじゃないかと一瞬気になるかもしれませんが、素因数として含まれる2の個数だけを取り扱っているので問題にはなりません。おまけに、{}_{2015} C_{m}は「組み合わせの数」を表してるので、全てかけ合わせれば必ず自然数になる。

*13:眠いのと、疲れてきたのとで、また今度確認にするかも。気が向いたら、更新します。

*14:k桁目に始めて0が現れるとする

*15:Nはある自然数