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

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

Komentarze

Dodaj nową odpowiedź