Пусть $0\le i_1\lt i_2\lt\ldots\lt i_n$ — целые числа. Докажите, что количество нечётных коэффициентов у многочлена
$$
(1+x)^{i_1}+(1+x)^{i_2}+\ldots+(1+x)^{i_n}
$$
не меньше, чем у многочлена $(1+x)^{i_1}$.
Будем называть два многочлена $F(x)$ и $G(x)$ с целыми коэффициентами эквивалентными, если все коэффициенты их разности $F(x)-G(x)$ чётны, и записывать эту эквивалентность так: $F(x)\equiv G(x)$. Например, $(1+x)^2\equiv 1+x^2$ (см. также формулы (1)—(4) на полях). Ясно, что если $F_1\equiv G_1$, $F_2\equiv G_2$, то $F_1+G_1\equiv F_2+G_2$, $F_1G_1\equiv F_2G_2$ ($F_1F_2-G_1G_2=F_1(F_2-G_2)+G_2(F_1-G_1)$) и $F_1^m\equiv G_1^m$ для любого натурального $m$. Число нечётных коэффициентов многочлена $F(x)$ будем обозначать через $W(F(x))$ или $W(F)$ и называть весом многочлена $F(x)$; положим $W((1+x)^i)=w(i)$. Многочлен $(1-x)^{i_1}+(1-x)^{i_2}+\ldots+(1+x)^{i_n}$ в условии задачи обозначим коротко через $P(x)$. Требуемое неравенство $w(i_1)\le W(P)$ можно доказать методом математической индукции. Вот одно из таких доказательств — индукцией по $i_n$ (предложенное авторами из Нидерландов, представившими эту задачу на международную олимпиаду).
$$
\begin{gather*}
(1+x)^2\equiv1+x^2,\quad\tag1\\[6pt]
(1+x)^2\equiv(1+x^2)^j,\quad\tag2\\[6pt]
(1+x)^{2j+1}\equiv(1+x^2)^j+x(1+x^2)^j,\quad\tag3\\[6pt]
(1+x)^{2j}+(1+x)^{2j+1}\equiv x(1+x^2)^j,\quad\tag4\\[6pt]
\end{gather*}
$$
формула (4) используется в случае $i_s=2j_s$, $i_{s+1}=i_s+1=2j_s+1$ ($s=1$, 2, $\ldots$, $m$).
Из формулы (1) на полях следует, что для любого многочлена с целыми коэффициентами степени меньше $q=2^k$
$$
W(F(x)(1+x)^q)=2W(F(x)).\tag{*}
$$
При $i_n=0$ и $i_n=1$ нужное неравенство $W(P)=w(i_1)$ очевидно. Предположим, что оно верно для $i_n\lt2^k$ ($k\ge1$) и докажем его для $2^k\le i_n\lt2^{k+1}$. Положим $q=2^k$ и рассмотрим два случая.
Если $i_1\ge 1$, то, полагая
$$
F(x)=(1+x)^{i_1-q}+\ldots+(1+x)^{i_n-q},
$$
по формуле (*) и предположению индукции получим:
$$
W(P)=2W(F)\ge2w(i_1-q)=w(i_1).
$$
Если $i_1\lt q$, запишем $P(x)$ в виде
$$
P_1(x)+(1+x)^qP_2(x)\equiv P_1(x)+P_2(x)+x^qP_2(x),
$$
где $P_1(x)$ — сумма многочленов $(1+x)^{i_s}$ с показателями $i_s\lt q$. Тогда каждый нечётный коэффициент многочлена $P_1$, который «убивается» нечётным коэффициентом $P_2$ при той же степени $x$, возникает вновь в члене степени на $q$ большей многочлена $x^qP_2(x)$, поэтому $w(i_1)\le W(P_1)\le W(P)$.
Приведём ещё одно рассуждение — индукцией по $i_1$. Для $i_1=0$ наше утверждение очевидно ($w(0)=1$).
Докажем, что если оно верно для некоторого $i_1=j_1$, то оно также верно для $i_1=2j_1$ и $i_1=2j_1+1$. Для этого, пользуясь предположением индукции и формулами (2), (3) и (4) на полях, учтём отдельно коэффициенты при чётных и нечётных степенях $x$ в многочленах $(1+x)^{i_1}$ и $P(x)$. Положив, в зависимости от чётности $i_s$, $i_s=2j_s$ или $i_s=2j_s+1$ и применяя формулы на полях, запишем многочлен $P(x)$ в виде $F_1(x^2)+xF_2(x^2)$.
Если $i_1=2j_1$, то, согласно (2), $w(i_1)=w(j_1)$. При этом, если $i_2\gt i_1+1$, то запись $P(x)$ начинается с $(1+x^2)^{j_1}$ и вклад коэффициентов при чётных степенях $x$ в вес $P(x)$ (т. е. вес $F_1(x)$) уже не меньше $w(j_1)$. Если же $i_2=i_1+1$, то, используя (4), мы начнём запись $P(x)$ с $x(1+x^2)^{j_1}$ и по предположению индукции вклад $W(F_2)$ коэффициентов при нечётных степенях $x$ в вес $P(x)$ не меньше $w(j_1)$.
Если $i_1=2j_1+1$, то, согласно (3), $w(i_1)=2w(j_1)$ и вклад в вес $P(x)$ и чётных, и нечётных степеней $x$ не меньше $w(j_1)$, так что $W(P)\ge2w(j_1)=w(i_1)$.
Наконец, наметим наиболее поучительное решение, использующее общее правило описания всех нечётных коэффициентов многочлена $(1+x)^i$. Представим $i$ в виде
$$
i=2^{m_1}+2^{m_2}+\ldots+2^{m_r},\quad m_1\lt m_2\lt\ldots\lt m_r;\tag{**}
$$
такое представление всегда существует и единственно ($m_1$, $\ldots$, $m_r$ — это номера разрядов двоичной записи числа $i$, в которых стоят 1). Тогда по формуле (1) на полях $(1+x)^i\equiv(1+x)^{q_1}\ldots(1+x)^{q_4}$, где $q_s=2^{m_s}$. Поэтому коэффициент $C_i^k$ многочлена $(1+x)^i$ при $x^k$ нечётен тогда и только тогда, когда $k$ равно некоторой подсумме суммы (**). Обозначая через $M(i)$ множество показателей $\{m_1,\ldots,m_r\}$ в двоичном разложении $i$, это условие можно записать в виде $M(k)\subset M(i)$. Следовательно, коэффициент при $x^k$ многочлена $P(x)$ нечётен тогда и только тогда, когда множество $B=M(k)$ содержится в нечётном числе множеств $A_s=M(i_s)$, $s=1$, 2, $\ldots$, $n$; такие множества $B$ будем называть нечётными. Итак, нужно доказать такой чисто комбинаторный факт: число всех подмножеств множества $A_1$ не меньше числа всех нечётных множеств. Для этого достаточно сопоставить всем $C\subset A_1$ различные нечётные подмножества $F(C)$.
Если $C$ само нечётно, положим $F(C)=C$. В противном случае добавим к $C$ множество, выбранное следующим образом. Рассмотрим все $A_s$, содержащие $C$ ($s\ge2$) — их число нечётно, — и множества $D_s$, состоящие из всех элементов $A_s$, не входящих в $A_1$. Среди этих множеств могут встретиться одинаковые; оставим лишь те, которые представлены нечётным числом копий, из них выберем некоторое наибольшее (не содержащееся в других) $D_h$ и положим $F(C)=C\cup D_h$. Легко видеть, что все множества $F(C)$ нечётны и различны ($F(C)\cap A_1=C$).
Если выписать коэффициенты $(1+x)^i$, заменяя чётные на 0, а нечётные — на 1, и составить из таких строчек таблицу, получится «двоичный треугольник Паскаля», показанный на полях. Попробуйте разобраться в его структуре и проследить с его помощью за последним решением.
