LII OM - III - Zadanie 6

Zawody matematyczne:

LII OM, 2000-2001

Etap:

III

Dane są liczby całkowite dodatnie $n_1 <n_2 < \ldots <n_{2000} < 10^{100}$ . Dowieść, że ze zbioru $\{n_1,n_2,\ldots,n_{2000}\}$ można wybrać niepuste rozłączne podzbiory $A$ i $B$ mające tyle samo elementów, taką samą sumę elementów i taką samą sumę kwadratów elementów.

Rozwiązanie

Dla zbioru $X \subseteq \{n_1,n_2,\ldots,n_{2000}\}$ niech $s_0(X)$ , $s_1(X)$ i $s_2(X)$ oznaczają odpowiednio liczbę elementów, sumę elementów i sumę kwadratów elementów zbioru $X$ .

Wystarczy udowodnić, że istnieją takie dwa różne podzbiory $C$ i $D$ zbioru $\{n_1,n_2,\ldots,n_{2000}\}$ , dla których $s_i(C) = s_i(D)$ dla $i = 0,1,2$ . Wówczas zbiory $A = C \setminus D$ oraz $B = D\setminus C$ są niepuste i spełniają warunki zadania.

Dla dowolnego podzbioru $X$ zbioru $\{n_1 , n_2, \ldots ,n_{2000}\}$ mamy

$<br /> (1) \qquad s_0(X) < 10^4,\ s_1(X) < 2000 \cdot 10^{100} < 10^{104}, s_2(X) < 2000\cdot 10^{200} < 10^{204}.<br />$

Oznaczając $S(X) = s_0(X) + 10^4s_1(X) + 10^{108}s_2(X)$ uzyskujemy

$<br /> S(X) < 10^{313} < (10^3)^{105} < 2^{1050} < 2^{2000} .<br />$

Stąd istnieją takie dwa różne podzbiory $C$ , $D$ zbioru $\{n_1 , n_2, \ldots ,n_{2000}\}$ , że $S(C) = S(D)$ . Z nierówności (1) wynika, że $s_i(C) = s_i(D)$ dla $i = 0, 1, 2$ , co kończy rozwiązanie zadania.