第3题

对于整数系数多项式

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

，记

w(P)

为奇数系数的个数。令

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

（

i=0,1,2,\ldots

）。证明：若

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 步：在二的幂边界处分割

上一步下一步

通俗地说

次数低于 $m$ 与高于 $m$ 的部分位于不同的抽屉。系数只有在两个奇贡献配对时才会消失，因此低位的两种描述合起来必须覆盖 $A$ 的每个奇系数。

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

详细分析

若 $i_1<m$ ，取 $r$ 使 $i_r<m<i_{r+1}$ ，令 $A=Q_{i_1}+\cdots+Q_{i_r}$ ，并把其余项写成 $(1+x)^mB$ ，其中 $\deg A,\deg B<m$ 。模 $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)$ 。