LVII OM - I - Zadanie 9

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

\[<br /> n =2^{k_1} +2^{k_2} +\dots+2^{k_m}.<br /> \]

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

\[<br /> P(x)=(x+1)^n .<br /> \]

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

\[<br /> \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)}<br /> \]

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ść

\[<br /> 2^j | p \Leftrightarrow 2^j | 2^k -p.<br /> \]

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

\[<br /> \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)}<br /> \]

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

\[<br /> \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)}<br /> \]

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

Z lematu wynika, że wielomian

\[<br /> (x+1)^{2^k} = x^{2^k} + \binom{2^k}{1} x^{2^{k-1}} + \dots + \binom{2^k}{2^k-1} x+1<br /> \]

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

\[<br /> (x+1)^n =(x+1)^{2^{k_1}} \cdot (x+1)^{2^{k_2}} \cdot \dots \cdot (x+1)^{2^{k_m}}<br /> \]

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

\[<br /> 2^{k_1} +\dots +2^{k_m} =2^{j_1} +\dots +2^{j_s}.<br /> \]

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:

\[<br /> \begin{split}<br /> 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 \\<br /> 2^{j_1} + \dots + 2^{j_s}.<br /> \end{split}<br /> \]

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

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź