XIX OM - I - Zadanie 5

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Dany jest zbiór $2n$ ( $n \geq 2$ ) różnych liczb. Jak podzielić ten zbiór na pary, żeby suma iloczynów liczb poszczególnych par była a) najmniejsza, b) największa?

Rozwiązanie

Przez podział zbioru liczb $Z$ na pary rozumiemy taki zbiór par liczb zbioru $Z$ , że każda liczba zbioru $Z$ należy do jednej i tylko jednej pary.

Oznaczmy dane liczby literami $a_1, a_2, \ldots, a_{2n}$ w taki sposób, że

$ (1) \qquad a_1< a_2< \ldots < a_{2n}. $

Liczba wszystkich podziałów zbioru liczb (1) na pary jest skończona, więc istnieje taki podział $P$ , dla którego suma iloczynów liczb poszczególnych par ma najmniejszą wartość. Oznaczmy tę sumę literą $S_P$ .

Jednym z wyrazów sumy $S_P$ musi być iloczyn $a_1a_{2n}$ . W sumie $S_P$ występuje bowiem wyraz $a_1a_k$ , którego jednym czynnikiem jest $a_1$ . Gdyby było $a_k \ne a_{2n}$ , wówczas suma $S_P$ miałaby inny wyraz z czynnikiem $a_{2n}$ , np. $a_la_{2n}$ , gdzie $l \ne k$ i $l \ne 1$ . Wtedy

$ \begin{split} a_1 a_k + a_la_{2n} & = a_1 a_{2n} + a_k a_l + (a_1 a_k - a_1 a_{2n}) + (a_l a_{2n} - a_k a_l) = \\ & = a_1 a_{2n} + a_1 (a_k - a_{2n}) + a_l(a_{2n} - a_k) = \\ & = a_1 a_{2n} + a_k a_l + (a_{2n} - a_k)(a_l - a_1), \end{split} $

więc na mocy (1) zachodziłaby nierówność

$ (2) \qquad a_1 a_k + a_l a_{2n} > a_1 a_{2n} + a_k a_l. $

W takim razie zastępując pary $(a_1, a_k)$ i $(a_l, a_{2n})$ podziału $P$ parami $(a_1, a_{2n})$ i $(a_k, a_l)$ otrzymalibyśmy taki podział $Q$ danych liczb na pary, przy których suma $S_Q$ iloczynów liczb poszczególnych par spełniałaby na skutek (2) nierówność

$ S_Q< S_P $

wbrew założeniu, że najmniejszą taką sumą jest $S_P$ .

Tak samo stwierdzamy, że suma $S_P - a_1a_{2n}$ musi mieć wyraz $a_2a_{2n-1}$ , suma $S_P -a_1a_{2n} - a_2a_{2n-1}$ - wyraz $a_3a_{2n-2}$ itd.

Zatem

$ S_P = a_1a_{2n} + a_2a_{2n-1} + \ldots + a_na_{n-1} $

tj. w podziale $P$ występują pary $(a_1 a_{2n}), (a_2, a_{2n-1}), \ldots, (a_n, a_{n-1})$ .

W analogiczny sposób dowodzi się, że największa suma $S_T$ iloczynów liczb poszczególnych par występuje przy podziale $T$ danego zbioru na pary $(a_1 a_2), (a_3, a_4),\ldots ,(a_{2n-1}, a_{2n})$ , tj. że

$ ST = a_1a_2 + a_3a_4 + \ldots + a_{2n-1} a_{2n}. $