XXXII - I - Zadanie 2

Zawody matematyczne:

XXXII OM, 1980-1981

Etap:

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

$ 2^{n_1}+2^{n_2}+\ldots + 2^{n_k} = 2^n $

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

$ 2^{n_1}+2^{n_2}+ \ldots + 2^{n_k}= 2^m $

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

$ \begin{array}{ll} (n) & 2^n\\ (n-1) & 2^{n-1}+2^{n-1}\\ (n-2) & 2^{n-2}+2^{n-2} +2^{n-2}+2^{n-2}\\ \vdots & \vdots\\ (2) & 2^2+2^2+\ldots+2^2\\ (1) & 2+2+\ldots+2\\ (0) & 1+1+\ldots+1 \end{array} $

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

$ 2^{n_1}+2^{n_2}+ \ldots + 2^{n_k} $

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.$