流れる空の中で数学を。

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

「2015東大理系 第５問」を２進法でガンガン解こうぜ！！ ～ついでに一般化できたかも？～

数学 プチ研究

Youtubeを散歩してたら……

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

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

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

2015東大理系　第5問

　問題は次の通り、

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

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

今回のあらすじ

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

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

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

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

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

　そこで、分母に現れるmが2でぴったり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^1は2で1回だけ割れるから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}回割れる。
よって、

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

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

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

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

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

　『驚愕の事実１: 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が犯人(正解)だったら、推理小説としては残念なレベル……
初見で感じた「オシャレ感」も３割りくらい引っ込めたい気持ちに*8……
一応結末は、この記事の最後ということで……


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

突然だが、ここで以下の数々を見比べていただきたい。
　11111011111_2と11111_2
　11111011011_2と11011_2
　11111010100_2と10100_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_0が0でないとする。
このとき、
X=111110 x_4 x_3 x_2 x_1 x_0
という２進数Xを考えると、Xを2で割れる最大回数は、x_4 x_3 x_2 x_1 x_0に一致する。」

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


以上をまとめて、

『定理２:２進法において、x_4 x_3 x_2 x_1 x_0を0でない自然数とする。このとき、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_2と31=11111_2
　2014=11111011110_2と30=11110_2

　　　　　　　　 \cdots

　2015-2^5+1=11111000001_2と1=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の場合は簡単に調べられるので、ステップ３へGO!

ステップ３：解法（m \lt 2^5のとき、 {}_{2015} C_{m}が奇数であること）

　m \lt 2^5の場合、定理２より、
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とする。

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

mを2で割れる最大の回数が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+1は2進数で表すと、その下k桁は1 0 \cdots 0に一致する。
　従って、11111_2-m+1とmが2で割り切れる最大の回数は等しい。
これより、31\cdots(31-m+1)が2で割り切れる最大の回数はm!と等しいので、

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

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

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

ステップ４：解法（ {}_{2015} C_{2^5}が偶数であること）

残すは、m=2^5の場合に、 {}_{2015} C_{m}が偶数になることを示したら終わりだ。これも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)!}はステップ３の結果より奇数なので、mと2015-m+1に含まれる素因数2の個数を比較すれば終わりである*12。

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

=11111011111_2-100000_2+1_2

=11111100000_2-100000_2

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

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

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

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

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

 

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

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

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

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

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

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

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

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

*9:2015の0の壁の左側の数のこと

*10:Nはある自然数

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

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

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

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

*15:Nはある自然数