【整数の旅１】
こんにちは、数学好きの独り言です。
今回から整数問題を取り扱っていきたいと思います。
整数論は数学の女王と呼ばれる分野で、非常に綺麗な世界が広がっています。
しかしその反面、高校生は苦手としている人が多く、授業での取り扱いも少ないため、対策が難しい分野としても有名です。
そこで整数の良問・難問を紹介していき、どのような思考で解くことができるか、解答はどのように書けばいいかを綴りたいと思います。扱う範囲は入試問題のみならず、数学オリンピックなど幅広く取り扱っていきます。
ヨビノリたくみさんの今週の積分のように、毎週出せていけたらいいなと思っています。
記念すべき第一回は、東大理系2015を解いていきます。
（問題）
m を2015以下の正の整数とする。2015Cm が偶数となる最小の m を求めよ。
二項係数に関する問題です。東大は数年に一度二項係数に関する問題を出題します。整数問題の中でも二項係数を扱う問題は難しいことが多いです。扱いに慣れていないことが原因であることも多いですが、単純に二項係数自体難易度が高いです。
予備校や個人で解いている人の解法をみると分数に直して素因数を考えていることが多いですが、ここでは二項定理を利用することで解いていきます。
では解いていきます。
まずは実験していきましょう。比較的小さい m では当然満たしません。時間があれば最悪片っ端から代入していって解けますが試験で解くのは現実的ではありませんね。
ここで二項係数の意味について考えます。二項係数が登場する式を考えると、当然二項定理があります。2015Cm は ( 1 + x )^2015 の x^m の係数ですね。すなわち、係数が初めて偶数となる小さい m を探せばよいことになります。
( 1 + x )^2015 を変形していきましょう。偶数かどうかを考えるので mod 2 で考えていきます。
突然ですが、数学の公式で一年生の夢と呼ばれるものを知っているでしょうか。展開の公式ですが、( a + b )^n = a^n + b^n というものです。通常これは成り立ちませんが、mod の世界なら成立します。今回は mod 2 なので ( 1 + x )^2 ≡ 1 + x^2 が成立することになります。これを用いて式変形していきましょう。
上記の公式を繰り返し用いることで、指数を減らすことができます。指数をすべて１にするように変形すると、x の肩に２の累乗が並びますが、唯一 ( 1 + x^32) だけ存在しないことになります。この変形後の式について考えてましょう。mod 2 で考えているということは、偶数の項はすべて消えています。すなわちこの式を展開したときに存在しない x^m の項こそ偶数である証拠になります。このうち最小のものを探します。そこで、補題として以下のものを示しておきます。
（補題）
すべての正の整数は、指数が非負整数である２の累乗の任意の和で表すことができる。
言っていることは少し複雑ですが、やっていることは単純です。２進法で考えれば当たり前ですね。
この事実を用いて考えると、変形後の式を展開したときに x^31 までの項は存在することが分かります。これはその係数がすべて奇数であるため消えなかったことを表しています。そして、x^32~63までは存在しないことが分かります。これはすなわちこの範囲では係数がすべて偶数であることを表しています。よって偶数となる最小の m は 32 ということが分かります。
（解説終わり）
いかがでしょうか。二項係数の意味から考え mod を使った変形をすることで求めることができました。この方法なら偶数となる二項係数やその数までも数えることができます。二項係数は二項定理から考えるのが自然なので覚えておくといいでしょう。
次回はこれを使って東大数学の中でも難問と呼ばれているもう一つの二項係数の問題を解いていきます。楽しみにしておいておください！