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

。

第 1/4 步：二的幂块只有两个奇系数

上一步下一步

通俗地说

二的幂指数使二项式模式分成低位拷贝和高位平移拷贝，两者之间不会发生奇偶抵消。

(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)$ 。