Komentarz

XXII OM - II - Zadanie 5

Dany jest zbiór liczb $ \{1, 2, 3, \ldots, 100\} $. Ze zbioru tego utworzyć 10 podzbiorów parami rozłącznych $ N_i = \{a_{i,1}, a_{i,2}, \ldots a_{i,10}} $ ($ i = 1, 2, \ldots, 10 $) tak, aby suma iloczynów

\[<br /> \sum_{i=10}^{10}\prod_{j=1}^{10} a_{i,j}<br /> \]

była największa.

Rozwiązanie

Udowodnimy najpierw następujący

Lemat. Jeżeli $ \{a_1, \ldots, a_r, b_1, \ldots, b_r \} $ jest zbiorem $ 2r $ różnych liczb dodatnich oraz $ a_i < b_j $ dla $ i,j = 1,2, \ldots,r $, to dla każdego $ k $ $ (1 \leq k < r) $

\[<br /> (1) \qquad a_1 \ldots a_kb_{k+1} \ldots b_r + b_1 \ldots b_k a_{k+1} \ldots a_r < a_1 \ldots a_r + b_1 \ldots b_r.<br /> \]

Inaczej mówiąc lemat stwierdza, że jeżeli dany zbiór jest rozbity na dwa podzbiory $ r $-elementowe, to suma iloczynów elementów należących do każdego z podzbiorów będzie największa, gdy każda liczba należąca do jednego z podzbiorów będzie mniejsza od każdej liczby należącej do drugiego.

Dowód. Przekształcamy nierówność (1) w sposób równoważny

\[<br /> a_1 \ldots a_k (b_{k+1} \ldots b_r - a_{k+1} \ldots a_r) < b_1 \ldots b_k - a_{k+1} \ldots a_r.<br /> \]
\[<br /> (2) \qquad (b_1 \ldots b_k - a_1 \ldots a_k) (b_{k+1} \ldots b_r - a_{k+1} \ldots a_r) > 0.<br /> \]

Z założenia mamy $ a_1 \ldots a_k < b_1 \ldots b_k $ oraz $ a_{k+1} \ldots a-r <b_{k+1} \ldots b_r $. Wynika stąd nierówność (2).

Przystępujemy teraz do rozwiązania zadania. Przypuśćmy, że podzbiory $ N_i $ ($ i =1,2, \ldots, 10 $) zbioru $ \{ 1, 2, 3, \ldots, 100\} $ spełniają warunki zadania. Wynika stąd w szczególności, że dla $ i \ne j $ zbiór $ N_i \cup N_j $ ma następującą własność: Jeżeli rozbić w dowolny sposób zbiór $ N_i \cup N_j $ na dwa podzbiory $ 10 $-elementowe, to suma iloczynów elementów należących do każdego z podzbiorów będzie największa wtedy, gdy tymi podzbiorami będą $ N_i $ i $ N_j $.

Z lematu wynika więc, że każda liczba należąca do zbioru $ N_i $ jest mniejsza od każdej liczby należącej do zbioru $ N_j $ lub odwrotnie. Zatem (zamieniając ewentualnie kolejność zbiorów $ N_i $) zbiory $ N_i $ spełniające warunki zadania mają następującą własność: Każda liczba należąca do zbioru $ N_i $ jest mniejsza od każdej liczby należącej do zbioru $ N_{i+1} $ dla $ i = 1,2, \ldots, 9 $. Wobec tego do $ N_1 $ należy $ 10 $ najmniejszych liczb zbioru $ \{1, 2, 3, \ldots, 100\} $, do $ N_2 $ - $ 10 $ następnych liczb naturalnych itd. Ogólnie $ N_i = \{10(i - 1) + j \colon j = 1, 2, \ldots, 10\} $ dla $ i = 1,2, \ldots, 10 $.

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

Dodaj komentarz