第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})

を証明せよ。

ステップ 3/4: 2 の冪の境界の上下に分ける

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

ざっくり言うと

次数 $m$ より下と $m$ より上は別の棚にある。係数が消えるのは二つの奇の寄与が対になるときだけなので、下の二つの記述を合わせれば $A$ の奇係数をすべて覆う。

w(A+B)+w(B)\ge w(A)

詳しい解説

$i_1<m$ なら、 $i_r<m<i_{r+1}$ となる $r$ をとり、 $A=Q_{i_1}+\cdots+Q_{i_r}$ とし、残りを $(1+x)^mB$ と書く。 $\deg A,\deg B<m$ である。mod $2$ では全体は $A+B+x^mB$ となり、次数範囲は交わらないから $w(Q)=w(A+B)+w(B)$ 。また $\mathbb F_2$ で $A=(A+B)+B$ なので、 $A$ の奇係数は少なくとも $A+B$ または $B$ の一方で奇であり、 $w(A+B)+w(B)\ge w(A)$ 。