XXXII - I - Zadanie 2

Dana jest liczba całkowita nieujemna $ n $. Dowieść, że liczba takich układów liczb całkowitych $ n_1 \geq n_2 \geq \ldots \geq n_k \geq 0 $, że

\[<br />
2^{n_1}+2^{n_2}+\ldots + 2^{n_k} = 2^n<br />
\]

jest nie mniejsza niż $ 2^n $.

Rozwiązanie

Przeprowadzimy dowód indukcyjny względem $ n $.

Dla $ n = 0 $ jest $ 2^0 = 1 $ i oczywiście układ zawierający jedyną liczbę $ 1 $ spełnia wymagania zadania.

Załóżmy, że dla każdej liczby całkowitej nieujemnej $ m $ mniejszej od liczby naturalnej $ n $ liczba układów $ n_1 \geq n_2 \geq \ldots \geq n_k \geq 0 $ spełniających

\[<br />
2^{n_1}+2^{n_2}+ \ldots + 2^{n_k}= 2^m<br />
\]

jest nie mniejsza niż $ 2^m $. Rozważmy liczbę $ 2^n $ i przedstawmy ją w następujący sposób:

\[<br />
\begin{array}{ll}<br />
(n)   & 2^n\\<br />
(n-1) & 2^{n-1}+2^{n-1}\\<br />
(n-2) & 2^{n-2}+2^{n-2} +2^{n-2}+2^{n-2}\\<br />
\vdots & \vdots\\<br />
(2) & 2^2+2^2+\ldots+2^2\\<br />
(1) & 2+2+\ldots+2\\<br />
(0) & 1+1+\ldots+1<br />
\end{array}<br />
\]

W każdym wierszu o numerze $ k $, prócz wierszy numer $ n $ oraz $ 0 $, można rozkładając ostatni składnik sumy zgodnie z założeniem indukcyjnym otrzymać nie mniej niż $ 2^{n-k} $ nowych rozkładów liczby $ 2^n $, przy czym wszystkie otrzymane w ten sposób rozkłady są różne. Wobec tego potrafimy przedstawić liczbę $ 2^n $ w wymaganej postaci na co najmniej $ 1 + 2^{n-1} + 2^{n-2} + \ldots + 2+1 $ sposobów. Ponieważ $ 2^{n-1} + 2^{n-2} + \ldots + 2+1=2^n-1 $, więc wykazaliśmy, że liczbę $ 2^n $ można przedstawić w postaci

\[<br />
2^{n_1}+2^{n_2}+ \ldots + 2^{n_k}<br />
\]

na nie mniej, niż $ 2^n $ sposobów.

Na mocy indukcji twierdzenie jest prawdziwe dla każdej liczby całkowitej nieujemnej $ n $.

Uwaga. Dla $ n= 0, 1, 2 $ liczba rozważanych tu rozkładów wynosi dokładnie $ 2^n $, natomiast dla $ n \geq 3 $ rozkładów takich jest więcej niż $ 2^n $, np. dla $ n = 3 $ mamy następujące rozkłady:

\[8,\]
\[4+4,\]
\[4+2+2,\]
\[4+2+1+1,\]
\[4+1 +1 +1 +1,\]
\[2+2+2+2,\]
\[2+2+2+1+1,\]
\[2+2+1+1+1+1,\]
\[2+1 + 1 + 1+1 + 1 + 1+1,\]
\[1+1 + 1+1 + 1 + 1 + 1 + 1.\]

Komentarze

Dodaj nową odpowiedź