XXII OM - II - Zadanie 5

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

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

$ \sum_{i=10}^{10}\prod_{j=1}^{10} a_{i,j} $

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)$

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

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

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

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

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