XIX OM - I - Zadanie 5

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

\[<br />
(1) \qquad  a_1< a_2< \ldots < a_{2n}.<br />
\]

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

\[<br />
\begin{split}<br />
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) = \\<br />
& = a_1 a_{2n} + a_1 (a_k - a_{2n}) + a_l(a_{2n} - a_k) = \\<br />
& = a_1 a_{2n} + a_k a_l + (a_{2n} - a_k)(a_l - a_1),<br />
\end{split}<br />
\]

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

\[<br />
(2) \qquad   a_1 a_k + a_l a_{2n} > a_1 a_{2n} + a_k a_l.<br />
\]

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ść

\[<br />
S_Q< S_P<br />
\]

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

\[<br />
S_P = a_1a_{2n} + a_2a_{2n-1} + \ldots + a_na_{n-1}<br />
\]

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

\[<br />
ST = a_1a_2 + a_3a_4 + \ldots + a_{2n-1} a_{2n}.<br />
\]

Komentarze

Dodaj nową odpowiedź