2項定理の応用？

▼ クリックで展開

2^2000通り

 

2001年日本数学オリンピック予選にて出題された問題です。天才的な閃きがなくても解ける問題だと思いましたので、紹介します。

 

では、解説です。

 

「選んだ数の総和が奇数となる」ということは、「奇数を奇数個」準備できればよいといことです。「奇数が偶数個あると偶数になる」からです。そして、偶数の数は何個であろうとどうでもよいです。

 

まずは簡単な偶数から行きましょう。

偶数は2,4,6,･･･2000までの1000個です。この1000個からn個選んで使う（n=0～1000）場合の数を出せばよいので、

 

1000C0+1000C1+1000C2+･･･+1000C1000=2^1000　：①

 

となります。

 

2項定理の(a+b)^n=Σ[r=0～n] nCr(a^n-r)*(b^r)　のaとbに1を代入した形です。

 

続いて、奇数です。これが曲者ですね。奇数は1,3,5,･･･2001までの1001個ですので、

 

1001C1+1001C3+1001C5+･･･+1001C1001

 

ですが、このままでは難しいです。

 

1001C0+1001C1+1001C2+1001C3+･･･+1001C1001=2^1001　：②

1001C0+1001C2+1001C4+1001C6+･･･+1001C1000　：③

 

とし、②から③を除去する形でいきましょう。

 

ここで、2項定理を応用します。

 

(a+b)^2m+1=Σ[r=0～2m+1] 2m+1Cr(a^2m+1-r)*(b^r)　　：Ⓐ

(-a+b)^2m+1=Σ[r=0～2m+1] 2m+1Cr(-a^2m+1-r)*(b^r)　：Ⓑ

 

Ⓐ-Ⓑの左辺は、

{(a+b)^2m+1}-{(-a+b)^2m+1}

 

右辺は、

2{2m+1C0(a^2m+1)*(b^0)+2m+1C2(a^2m+1-2)*(b^2)+2m+1C4(a^2m+1-4)*(b^4)+･･･2m+1C2m(a^2m+1-2m)*(b^2m)}

 

となります。ここで、a=1,b=1,m=500を代入すると、

 

(2^1001)-(0^1001)=2*(1001C0+1001C2+1001C4+･･･1001C1000)　となりますので、

 

1001C0+1001C2+1001C4+･･･1001C1000=(2^1001)/2

 

つまり、③は2^1000であることがわかります。

 

したがって、①×（②-③）が求める答えですので、

 

2^1000*(2^1001-2^1000)=2^1000*2^1000=2^2000　となります。

 

2項定理の応用ができる良い問題ですね。と思っていましたら、天才たちは次のように解くようです。

 

1～2000までは適当に選んで（選んでもよいし、選ばなくてもよいのでそれぞれ2択）、2^2000通り。

 

ここで、2001は、適当に2000まで選んできた数の総和が「偶数だったら選択」「奇数だったら選択しない」と使い方は必ず1通りに決められる。

 

したがって、2^2000*1=2^2000通り。

 

すごくエレガントですね。これを一瞬で閃ける人は本当にすごいと思います。