XXVIII - I - Zadanie 8

Dowieść, że zbiór $ \{1, 2, \ldots, 2^{s+1}\} $ można tak rozbić na dwa zbiory $ 2s $-elementowe $ \{x_1, x_2, \ldots, x_{2^s}\} $, $ \{y_1, y_2, \ldots, y_{2^s}\} $, że dla każdego naturalnego $ j \leq s $ zachodzi równość

\[<br />
\sum_{i=1}^{2^s} x_i^j = \sum_{i=1}^{2^s} y_i^j.<br />
\]

Rozwiązanie

Zastosujemy indukcję względem $ s $. Dla $ s = 1 $ mamy zbiór $ \{1, 2, 3, 4\} $. Rozbijając go na podzbiory $ \{1, 4\} $ i $ \{2, 3\} $ będziemy mieli spełnione warunki zadania, ponieważ $ 1 + 4 = 2 + 3 $.

Załóżmy z kolei, że dla pewnej liczby naturalnej $ s $ istnieje takie rozbicie zbioru $ \{1, 2, \ldots, 2^{s+1}\} $ na podzbiory $ \{x_1, x_2, \ldots, x_{2^s}\} $ i $ \{y_1, y_2, \ldots, y_{2^s}\} $, że

\[<br />
(1) \qquad \sum_{i=1}^{2^s} x_i^j = \sum_{i=1}^{2^s} y_i^j \ \textrm{dla} \ j = 1, 2, \ldots, s.<br />
\]

Wtedy

\[<br />
\begin{split}<br />
\{1&, 2, \ldots, 2^{s+2}\} =<br />
\{1, 2, \ldots, 2^{s+1}\} \cup \{2^{s+1} + 1, 2^{s+1} + 2, \ldots, 2^{s+1} + 2^{s+1}\} =\\<br />
&=\{x_1, x_2, \ldots, x_{2^s}, y_1, y_2, \ldots, y_{2^s}\}\cup\\<br />
&\quad \cup \{ x_1 + 2^{s+1}, x_2 + 2^{s+1}, \ldots, x_{2^s} + 2^{s+1}, y_1- 2^{s+1}, y_2 + 2^{s+1}, \ldots,<br />
y_{2^s} + 2^{s+1} \}.<br />
\end{split}<br />
\]

Udowodnimy, że rozbicie zbioru $ \{1, 2, \ldots, 2^{s+2} \} $ na podzbiory

\[<br />
\{x_1, x_2, \ldots, x_{2^s}, y_1 + 2^{s+1}, y_2 + 2^{s+1}, \ldots, y_{2^s} + 2^{s+1} \}<br />
\]

oraz

\[<br />
\{y_1, y_2, \ldots, y_{2^s}, x_1 + 2^{s+1}, x_2 + 2^{s+1}, \ldots, x_{2^s} + 2^{s+1} \}<br />
\]

spełnia warunki zadania.

Dla $ r = 1, 2, \ldots, s + 1 $ na mocy wzoru dwumianowego suma $ r $-tych potęg elementów pierwszego podzbioru jest równa

\[<br />
\begin{split}<br />
\sum_{i=1}^{2^s} x_i^r + \sum_{i=1}^{2^s} (y_i & + 2^{s+1})^r =<br />
\sum_{i=1}^{2^s} x_i^r +<br />
\sum_{i=1}^{2^s} \left( \sum_{j=0}^{r-1} \binom{r}{j} y_i^j \cdot 2^{(s+1)(r-j)} + y_i^r \right) =\\<br />
& = \sum_{i=1}^{2^s} x_i^r + \sum_{j=0}^{r-1} \binom{r}{j} 2^{(s+1)(r-j)}<br />
\sum_{i=1}^{2^s} y_i^j + \sum_{i=1}^{2^s} y_i^r.<br />
\end{split}<br />
\]

Analogicznie obliczamy sumę $ r $-tych potęg elementów drugiego podzbioru:

\[<br />
\begin{split}<br />
\sum_{i=1}^{2^s} y_i^r + \sum_{i=1}^{2^s} (x_i & + 2^{s+1})^r =<br />
\sum_{i=1}^{2^s} y_i^r +<br />
\sum_{i=1}^{2^s} \left( \sum_{j=0}^{r-1} \binom{r}{j} x_i^j \cdot 2^{(s+1)(r-j)} + x_i^r \right) =\\<br />
& = \sum_{i=1}^{2^s} y_i^r + \sum_{j=0}^{r-1} \binom{r}{j} 2^{(s+1)(r-j)}<br />
\sum_{i=1}^{2^s} x_i^j + \sum_{i=1}^{2^s} x_i^r.<br />
\end{split}<br />
\]

Porównując otrzymane wyniki stwierdzamy, że różnią się one tylko tym, że w jednym wzorze występuje suma

\[<br />
\sum_{i=1}^{2^s} y_i^j,\ \textrm{a w drugim}\ \sum_{i=1}^{2^s} x_i^j,\ \textrm{gdzie}\ 0 \leq j \leq r - 1 \leq s.<br />
\]

Ze wzoru (1) wynika, że sumy te są równe.

Komentarze

Dodaj nową odpowiedź