LII OM - III - Zadanie 6

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.

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

Komentarze

Dodaj nową odpowiedź