Fussy's Diary:2016年08月14日

2016年08月14日

盆休み

お盆休みに入りましたが、相変わらず蒸し暑い日が続きます。明日は雨のようですね。さらに湿度が上がりそうな予感が。。。

「数学問題bot(個人用)」から東大の問題を解いてみました。例によって合っている保証はありません。

-----

0 ≤ n ≤ m を満たすすべての整数 n について、_mC_n が奇数となる m を求めよ ( 1999年東大 )

_mC_n については以下の定理が成り立ちます。

_mC₀ = 1
_mC₁ = m
_m+1C_n = _mC_n-1 + _mC_n
_mC_n = _mC_m-n

3 番目はいわゆる「パスカルの三角形」で、_mC_n を m = 0 を一番上にして下へ順番に、n = 0 を一番左側にして右の方へ順番に並べると以下の様な三角形ができます。

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
:

実際は正三角形の形に表しますが、面倒なので上のような書き方にしています。頂上から順に、x, x + y, ( x + y )² ... を展開したときの係数と等しく、上側の二つの値を足すと下側の値になります。また、左右対称の形になっているのは先に示した 4 番目の式を表します。

パスカルの三角形を見ると、すでに m = 0, 1, 3, 7 のときに各係数は奇数となっているので、この結果から m = 2^k - 1 ( k > 0 ) が解答であることが予想できます。そこで、_2^k-1-1C_n について命題が成り立つと仮定すると、

_2^k-1C_n
= ( 2^k - 1 )! / ( 2^k - n - 1 )!n!
= ( 2^k - 1 )( 2^k - 2 )...2^k-1( 2^k-1 - 1 )! / ( 2^k - n - 1 )( 2^k - n - 2 )...( 2^k-1 - n )( 2^k-1 - n - 1 )!n!
= [ ( 2^k - 1 )( 2^k - 2 )...2^k-1 / ( 2^k - n - 1 )( 2^k - n - 2 )...( 2^k-1 - n ) ]_2^k-1-1C_n

となるので、

_kL_n = ( 2^k - 1 )( 2^k - 2 )...2^k-1 / ( 2^k - n - 1 )( 2^k - n - 2 )...( 2^k-1 - n )

として、_kL_n が奇数であることを証明します。まず、明らかに _kL₀ = 1 です。また、分子の第一項は奇数であり、最後の項は偶数で、分子・分母ともに 2^k-1 個の項の積となっています。分子は

( 2^k - 1 )( 2^k - 2 )...2^k-1
= ( 2^k - 1 )・2( 2^k-1 - 1 )・( 2^k - 3 )・2²( 2^k-2 - 1 )...2^k-1
= 2^k(k-1)/2(odd) ( 但し (odd) は奇数 )

で表せます。従って、分母に対しても 2 が k( k - 1 ) / 2 個あることが示されれば _kL_n は奇数であることになります。まず、n = 0 のときは分子・分母はともに等しくなるので成り立ちます。そこで、n のときに成り立っていると仮定します。このとき、n = 0 の場合に対して前側の項は n 個分少なくなり、同時に末尾には n 個の項が増えた形になります。n が奇数なら先頭は偶数、末尾は奇数であり、n が偶数ならその逆で、偶奇は交互に現れます。

	( 2^k - n - 1 )	( 2^k - n - 2 )	...	( 2^k-1 - n )
n が奇数	偶	奇		奇
n が偶数	奇	偶		偶

n + 1 のときは、先頭の項がなくなり、末尾に項が一つ増えます。n が偶数のときは奇数の項が増減するだけなので 2 のべき数は変化しません。n が奇数のとき、2^k - n - 1 がなくなり、2^k-1 - n - 1 が増えます。n + 1 は偶数なので、これを 2^pq ( 但し q は奇数 ) とすると、

2^k - n - 1 = 2^k - 2^pq = 2^p( 2^k-p - q )
2^k-1 - n - 1 = 2^k-1 - 2^pq = 2^p( 2^k-p-1 - q )

なのでやはり 2 のべき数は変わりません。

よって、帰納法により _kL_n は奇数であることになり、命題が証明されました。

係数を偶数は .　奇数は o としてパスカルの三角形を書くと以下のようになります。