对任意整系数多项式 $P(x)={a}_{0}+{a}_{1}x+…+{a}_{k}{x}^{k}$．用 $W(P)$ 表示 $P(x)$ 中系数为奇数的个数，考虑多项式 ${Q}_{i}(x)={(1+x)}^{i},i=0,1,2,\cdots$
如果 ${i}_{1},{i}_{2},\cdots,{i}_{n}$ 都是整数且 $0\leqslant {i}_{1}<{i}_{2}<\cdots<{i}_{n}$，求证：$W({{Q}_{{{i}_{1}}}}+{{Q}_{{{i}_{2}}}}+\cdots +{{Q}_{{{i}_{n}}}})\geqslant W({{Q}_{{{i}_{1}}}})$．（荷兰）
如果 ${i}_{1},{i}_{2},\cdots,{i}_{n}$ 都是整数且 $0\leqslant {i}_{1}<{i}_{2}<\cdots<{i}_{n}$，求证：$W({{Q}_{{{i}_{1}}}}+{{Q}_{{{i}_{2}}}}+\cdots +{{Q}_{{{i}_{n}}}})\geqslant W({{Q}_{{{i}_{1}}}})$．（荷兰）
【难度】
【出处】
1985年第26届IMO试题
【标注】
【答案】
略
【解析】
首先建立两个引理．
设 $R,S$ 是两个整系数多项式，$m$ 是正整数，则有：
引理一：如果 $k=2^{m}$，则 $(1+x)^k\equiv 1+x^k\pmod{2}$；
引理二：如 $R$ 的次数（最高次数项的次数）小于 $k$，则 $W(R+x^kS)=W(R)+W(S)$．
这两个引理是显然成立的．
当 $i_n=0,1$ 时，结论明显成立．
当 $i_n>1$ 时，记 $Q=Q_{i_1}+Q_{i_2}+\cdots+Q_{i_n}$，不妨设 $k=2^m\leqslant i_n<2^{m+1}$．
分两种情况讨论．
（$i$）$i_1<k$，设 $i_r<k\leqslant i_{r+1}$，则 $Q=R+(1+x)^kS$．
其中 $R=Q_{i_1}+Q_{i_2}+\cdots+Q_{i_r},S=(1+x)^{-k}(Q_{i_{r+1}}+Q_{i_{r+2}}+\cdots+Q_{r_n})$．
$R,S$ 的次数均小于 $k$．则由引理一，$(1+x)^k$ 中不影响奇系数的只有 $1$ 和 $x^k$ 两项．于是
$\begin{aligned}
W(Q)&=W(R+(1+x)^kS)\\
&=W(R+S+x^kS)\\
&=W(R+S)+W(S)\\
&\geqslant W(R)
\end{aligned}$
最后一步是因为"三角形不等式"，可以这样理解，本来 $R$ 有 $W(R)$ 个奇数项，$R$ 加上 $S$ 后有 $t$ 个变成了偶数项，那么 $S$ 至少有 $t$ 个奇数项，即
$W(R+S)\geqslant W(R)-t$
$W(S)\geqslant t$
两式一加即可．
由第二归纳法假设，知 $W(R)\geqslant W(Q_{i_1})$
于是 $W(Q)\geqslant W(Q_{i_1})$ 成立．
（$ii$）$i_1\geqslant k$．令 $Q_{i_1}=(1+x)^kR,Q=(1+x)^k$，则 $R$ 和 $S$ 的次数均小于 $k$，则
$\begin{aligned}
W(Q)&=W(S+x^kS)\\
&=2W(S)\\
&\geqslant 2W(R)\\
&=W(R+x^kR)\\
&=W(Q_{i_1})
\end{aligned}$
证毕．
设 $R,S$ 是两个整系数多项式，$m$ 是正整数，则有：
引理一：如果 $k=2^{m}$，则 $(1+x)^k\equiv 1+x^k\pmod{2}$；
引理二：如 $R$ 的次数（最高次数项的次数）小于 $k$，则 $W(R+x^kS)=W(R)+W(S)$．
这两个引理是显然成立的．
当 $i_n=0,1$ 时，结论明显成立．
当 $i_n>1$ 时，记 $Q=Q_{i_1}+Q_{i_2}+\cdots+Q_{i_n}$，不妨设 $k=2^m\leqslant i_n<2^{m+1}$．
分两种情况讨论．
（$i$）$i_1<k$，设 $i_r<k\leqslant i_{r+1}$，则 $Q=R+(1+x)^kS$．
其中 $R=Q_{i_1}+Q_{i_2}+\cdots+Q_{i_r},S=(1+x)^{-k}(Q_{i_{r+1}}+Q_{i_{r+2}}+\cdots+Q_{r_n})$．
$R,S$ 的次数均小于 $k$．则由引理一，$(1+x)^k$ 中不影响奇系数的只有 $1$ 和 $x^k$ 两项．于是
$\begin{aligned}
W(Q)&=W(R+(1+x)^kS)\\
&=W(R+S+x^kS)\\
&=W(R+S)+W(S)\\
&\geqslant W(R)
\end{aligned}$
最后一步是因为"三角形不等式"，可以这样理解，本来 $R$ 有 $W(R)$ 个奇数项，$R$ 加上 $S$ 后有 $t$ 个变成了偶数项，那么 $S$ 至少有 $t$ 个奇数项，即
$W(R+S)\geqslant W(R)-t$
$W(S)\geqslant t$
两式一加即可．
由第二归纳法假设，知 $W(R)\geqslant W(Q_{i_1})$
于是 $W(Q)\geqslant W(Q_{i_1})$ 成立．
（$ii$）$i_1\geqslant k$．令 $Q_{i_1}=(1+x)^kR,Q=(1+x)^k$，则 $R$ 和 $S$ 的次数均小于 $k$，则
$\begin{aligned}
W(Q)&=W(S+x^kS)\\
&=2W(S)\\
&\geqslant 2W(R)\\
&=W(R+x^kR)\\
&=W(Q_{i_1})
\end{aligned}$
证毕．
答案
解析
备注
