第3問

整数係数多項式

P(x)=a_0+a_1x+\cdots+a_kx^k

に対し、奇数である係数の個数を

w(P)

とする。

i=0,1,2,\ldots

に対して

Q_i(x)=(1+x)^i

とおく。

0\le i_1<i_2<\cdots<i_n

ならば、

w(Q_{i_1}+Q_{i_2}+\cdots+Q_{i_n})\ge w(Q_{i_1})

を証明せよ。

ステップ 1/4: 2 の冪のブロックには奇係数が二つだけ

前のステップ次のステップ

ざっくり言うと

2 の冪の指数では二項係数のパターンが低いコピーと高いコピーに分かれ、両者の間で奇偶が打ち消し合わない。

(1+x)^m\equiv1+x^m\pmod 2\quad(m=2^r)

詳しい解説

$m=2^r$ ならば、内部の二項係数 $\binom mr$ はすべて偶数である。これは $(1+x)^{2t}\equiv(1+x^2)^t\pmod2$ を繰り返せば得られ、 $(1+x)^m\equiv1+x^m\pmod2$ となる。次数が $m$ 未満の多項式を掛ければ二つのコピーの次数範囲は交わらず、 $w((1+x)^mA)=2w(A)$ である。