XXII OM - I - Zadanie 10

Dana jest tablica o $ n $ wierszach i $ n $ kolumnach. Liczba znajdująca się w $ m $-tej kolumnie i $ k $-tym wierszu równa jest $ n(k - 1) + m $. Jak należy wybrać $ n $ liczb, po jednej z każdego wiersza i każdej kolumny, aby iloczyn tych liczb był największy ?

Rozwiązanie

Oznaczmy $ a_{k,m} = n (k - 1) + m $, gdzie $ 1 \leq k, m \leq n $. Przypuśćmy, że z $ i $-tego wiersza wybieramy liczbę stojącą w kolumnie o numerze $ m_i $, gdzie $ i = 1, 2, \ldots, n $. Z warunków zadania wynika, że ciąg $ m_1, m_2, \ldots, m_n $ ma różne wyrazy. Każdemu takiemu ciągowi odpowiada iloczyn $ a_{1m_1} \cdot a_{2m_2} \cdot \ldots \cdot a_{nm_n} $.

Udowodnimy, że jeżeli ciąg $ m_1, m_2, \ldots, m_n $ nie jest malejący, to odpowiadający mu iloczyn nie jest największy.

Niech na przykład $ m_i < m_{i+1} $ dla pewnego $ i $. Rozważmy iloczyny $ A $ i $ B $ odpowiadające ciągom:

\[<br />
m_1, \ldots, mi, m_{i + 1}, \ldots, m_n<br />
\]

oraz

\[<br />
m_1, \ldots,m_{i+1}, m_i, \ldots,m_n<br />
\]

(ciągi te różnią się tylko wyrazami o numerach $ i $ oraz $ i + 1 $). Zatem

\[<br />
A = a_{1m_1} \ldots a_{im_i} a_{i+1m_{i+1}} \ldots a_{n m_n}=<br />
\prod_{k \ne i, i+1} a_{km_k} \cdot a_{im_i} a_{i+1 m_{i+1}}<br />
\]

oraz

\[<br />
B = a_{1m_1} \ldots a_{im_{i+1}} a_{i+1m_i} \ldots a_{n m_n}=<br />
\prod_{k \ne i, i+1} a_{km_k} \cdot a_{im_{i+1}} a_{i+1 m_i}.<br />
\]

Oznaczając $ \displaystyle C= \prod_{k \ne i, i+1} a_{km_k} $ i wykorzystując określenie liczb $ a_{km} $ otrzymujemy:

\[<br />
\begin{split}<br />
B - A &= C (a_{im_{i+1}} a_{i+1m_i} - a_{im_i} a_{i+1m_{i+1}}=\\<br />
&=C [ (n (i - 1) + m_{i+1}) (ni + m_i) -(n(i- 1) + m_i)(ni + m_{i+1}] =\\<br />
&= C (m_{i+1} - m_i) > 0.<br />
\end{split}<br />
\]

Zatem $ B > A $, tzn. iloczyn odpowiadający drugiemu ciągowi jest większy niż iloczyn odpowiadający pierwszemu. Dowiedliśmy więc, że jeżeli ciąg $ m_1, m_2, \ldots, m_n $ nie jest malejący, to odpowiadający mu iloczyn nie jest największy. Wobec tego największy iloczyn odpowiada ciągowi malejącemu. Ponieważ z liczb $ 1, 2, \ldots, n $ można tylko na jeden sposób utworzyć $ n $-wyrazowy ciąg malejący, mianowicie ciąg $ n, n - 1, \ldots, 2, 1 $, więc największy iloczyn jest równy $ a_{1n}a_{2n-1} \ldots a_{n1} = n(2n - 1) (3n - 2) (4n - 3) \ldots (n^2 - (n -1)) $.

Komentarze

Dodaj nową odpowiedź