XXVIII - I - Zadanie 8

Zawody matematyczne:

XXVIII OM, 1976-1977

Etap:

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

$ \sum_{i=1}^{2^s} x_i^j = \sum_{i=1}^{2^s} y_i^j. $

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

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

Wtedy

$ \begin{split} \{1&, 2, \ldots, 2^{s+2}\} = \{1, 2, \ldots, 2^{s+1}\} \cup \{2^{s+1} + 1, 2^{s+1} + 2, \ldots, 2^{s+1} + 2^{s+1}\} =\\ &=\{x_1, x_2, \ldots, x_{2^s}, y_1, y_2, \ldots, y_{2^s}\}\cup\\ &\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, y_{2^s} + 2^{s+1} \}. \end{split} $

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

$ \{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} \} $

oraz

$ \{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} \} $

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

$ \begin{split} \sum_{i=1}^{2^s} x_i^r + \sum_{i=1}^{2^s} (y_i & + 2^{s+1})^r = \sum_{i=1}^{2^s} x_i^r + \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) =\\ & = \sum_{i=1}^{2^s} x_i^r + \sum_{j=0}^{r-1} \binom{r}{j} 2^{(s+1)(r-j)} \sum_{i=1}^{2^s} y_i^j + \sum_{i=1}^{2^s} y_i^r. \end{split} $

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

$ \begin{split} \sum_{i=1}^{2^s} y_i^r + \sum_{i=1}^{2^s} (x_i & + 2^{s+1})^r = \sum_{i=1}^{2^s} y_i^r + \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) =\\ & = \sum_{i=1}^{2^s} y_i^r + \sum_{j=0}^{r-1} \binom{r}{j} 2^{(s+1)(r-j)} \sum_{i=1}^{2^s} x_i^j + \sum_{i=1}^{2^s} x_i^r. \end{split} $

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

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

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