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.

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

Komentarze

Dodaj nową odpowiedź