Evolton

東京大学 2015年度 前期日程 第2次学力試験理系数学 第5問

mを2015以下の正の整数とする。
2015Cmが偶数となる最小のmを求めよ。

難易度6/ 10計算量4/ 10目安15分

場合の数、整数 偶奇性、約数・倍数、範囲評価

方針

2015Cm を 2015⋅2014⋯(2016−m)m! と書き、分子の因数 2016−j と分母の因数 j に含まれる2の個数を比較する。2016=25⋅63 なので、1≦j≦31 では j と 2016−j に含まれる2の個数が一致する。したがって m≦31 は奇数であり、m=32 で初めて分子側の2の個数が1つ多くなることを示す。

解答

2016=32⋅63=25⋅63 である。

1≦j≦31 とする。j に含まれる因数 2 の個数を r とすると、j<32 だから 0≦r≦4 であり j=2rs と書ける。ただし s は奇数である。このとき 2016−j=2r(20162r−s) である。r≦4 より 2016/2r は偶数であり、s は奇数なので 20162r−s は奇数である。したがって、2016−j に含まれる因数 2 の個数も r である。

1≦m≦31 のとき2015Cm=2015⋅2014⋯(2016−m)m!=(2016−1)(2016−2)⋯(2016−m)1⋅2⋯mである。上で示したように、各 j=1,2,…,m について、分子の因数 2016−j と分母の因数 j に含まれる因数 2 の個数は等しい。したがって分子全体と分母全体に含まれる因数 2 の個数も等しく、約分後に因数 2 は残らない。ゆえに 2015Cm は奇数である。

次に m=32 を調べる。j=1,2,…,31 に対応する部分では、先ほどと同様に因数 2 の個数は分子と分母で等しい。残る j=32 に対しては 2016−32=1984=26⋅31 である。一方、分母側の因数は 32=25 である。したがって j=32 の部分で分子側に因数 2 が1個多く、全体として 2015C32 は偶数である。

以上より、2015Cm が偶数となる最小の m は 32 である。

別解

解法2(2を法とする多項式)

方針

二項展開の係数を2で割った余りだけ考える。(1+x)2k の中間係数がすべて偶数であることから、指数2015の2進表示を使って (1+x)2015 を2を法として因数分解する。係数が奇数になる次数を、選べる2の冪の和として判定する。

解答

多項式の係数を2で割った余りで考える。二項係数の対称性とパスカルの関係、または二項展開を繰り返すことにより、正の整数 k について(1+x)2k≡1+x2k(mod2)が成り立つ。

2015の2進表示は2015=1024+512+256+128+64+16+8+4+2+1であり、32 の位だけが欠けている。したがって(1+x)2015≡(1+x1024)(1+x512)(1+x256)⋅(1+x128)(1+x64)(1+x16)(1+x8)⋅(1+x4)(1+x2)(1+x)(mod2)である。

右辺を展開すると、各因子から 1 または x2j を選ぶ。異なる選び方は2進表示の一意性により異なる次数を与えるので、ある次数 m の係数が奇数であるための必要十分条件は、m の2進表示で1となる桁が、上に並んだ桁だけからなることである。

1≦m≦31 では使う桁は 1,2,4,8,16 だけであり、これらの因子はすべて存在する。よって2015Cm≡1(mod2)(1≦m≦31)である。

一方、m=32 の2進表示は 100000 であり、必要な x32 の因子が存在しない。したがって2015C32≡0(mod2)である。以上より、偶数となる最小の m は32である。

総評

難度6、計算量4。目安時間は15分。二項係数の偶奇を扱う問題である。第1解法は分子と分母に含まれる2の個数を一つずつ比較し、第2解法は (1+x)2015 を2を法として展開して2進表示から判定する。2015 ではなく 2016=25⋅63、または2015の2進表示で 32 の位だけが0であることに注目するのが決め手である。前者では 1984=26⋅31 と 32=25 の差、後者では2進表示の一意性を明示すると、m=32 が最小であることがはっきりする。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る東大の場合の数の問題で問題集を作る

出典: 東京大学 2015年度 第2次学力試験 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。