LVII OM - I - Zadanie 9

Zawody matematyczne:

LVII OM, 2005-2006

Etap:

Dane są nieujemne liczby całkowite $k_1 <k_2 <\dots <k_m$ . Niech

$ n =2^{k_1} +2^{k_2} +\dots+2^{k_m}. $

Wyznaczyć liczbę nieparzystych współczynników wielomianu

$ P(x)=(x+1)^n . $

Rozwiązanie

Na początku udowodnimy następujący lemat:

Lemat

Jeśli $1 \leq t \leq 2^k$ , to liczba $\binom{2^k}{t}$ jest parzysta.

Dowód

Zauważmy, że

$ \binom{2^k}{t} = \frac{2^k \cdot (2^k -1)\cdot (2^k -2)\cdot \dots \cdot (2^k -(t -2)) \cdot (2^k -(t-1))}{t \cdot 1\cdot 2\cdot ...\cdot (t-2)\cdot (t-1)} $

Następnie, dla dowolnych liczb $j$ i $p$ takich, że $1\leq j \leq k$ oraz $1\leq p<t$ zachodzi następująca równoważność

$ 2^j | p \Leftrightarrow 2^j | 2^k -p. $

Stąd wynika, że w rozkładzie liczb $p$ i $2^k -p$ na czynniki pierwsze, liczba 2 występuje w tej samej potędze. Zatem liczba 2
występuje w tej samej potędze w liczniku i mianowniku ułamka

$ \frac{(2^k -1)\cdot (2^k -2)\cdot \dots \cdot (2^k -(t -2)) \cdot (2^k -(t-1))}{1\cdot 2\cdot ...\cdot (t-2)\cdot (t-1)} $

Ponieważ $t<2^k$ , więc liczba 2 występuje w rozkładzie liczby $t$ w potędze o wykładniku mniejszym od $k$ . Zatem w liczniku ułamka $\frac{2^k}{t}$ występuje więcej dwójek niż w mianowniku, co dowodzi, że ułamek

$ \frac{2^k \cdot (2^k -1)\cdot (2^k -2)\cdot \dots \cdot (2^k -(t -2)) \cdot (2^k -(t-1))}{t \cdot 1\cdot 2\cdot ...\cdot (t-2)\cdot (t-1)} $

(po skróceniu) jest liczbą parzystą. To kończy dowód lematu.

Z lematu wynika, że wielomian

$ (x+1)^{2^k} = x^{2^k} + \binom{2^k}{1} x^{2^{k-1}} + \dots + \binom{2^k}{2^k-1} x+1 $

ma dokładnie dwa współczynniki nieparzyste: przy $x$ w najwyższej potędze oraz jedynkę. Stąd wynika, że w wielomianie

$ (x+1)^n =(x+1)^{2^{k_1}} \cdot (x+1)^{2^{k_2}} \cdot \dots \cdot (x+1)^{2^{k_m}} $

jedyne współczynniki nieparzyste mogą wystąpić przy iloczynach postaci $x^{2^{k_{i_1}}}\cdot \dots \cdot x^{2^{k_{i_j}}}$
(a także przy iloczynie jedynek). Takich iloczynów (łącznie z iloczynem jedynek) jest $2^m$ . Musimy tylko udowodnić, że
nie nastąpi redukcja wyrazów podobnych zmniejszająca liczbę współczynników nieparzystych. Wynika to z następującego lematu:

Lemat

Jeśli $k_1 <k_2 <\dots <k_m$ , $j_1 <j_2 <\dots <j_s$ oraz ciągi $(k_1,\dots ,k_m)$ i $(j_1,\dots ,j_s)$ są różne, to
$2^{k_1}+\dots +2^{k_m} \neq 2^{j_1}+\dots+2^{j_s}$ .

Dowód

Przypuśćmy, że

$ 2^{k_1} +\dots +2^{k_m} =2^{j_1} +\dots +2^{j_s}. $

Jeśli $2^{k_m} = 2^{j_s}$ , to w powyższej równości możemy skrócić najwyższe potęgi. Bez zmniejszenia ogólności możemy więc
założyć, że najwyższe potęgi są różne, np. $2^{k_m} > 2^{j_s}$ . Mamy wtedy:

$ \begin{split} 2^{k_1} + \dots + 2^{k_m} \geq 2^{k_m} > 2^{k_m} -1 = 2^{k_m-1} +2^{k_m-2} +\dots + 2^2 + 2^1 + 1 \geq \\ 2^{j_1} + \dots + 2^{j_s}. \end{split} $

To kończy dowód lematu i tym samym dowodzi, że wielomian $(x + 1)^n$ ma $2^m$ współczynników nieparzystych.