XXII OM - I - Zadanie 10

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

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:

$ m_1, \ldots, mi, m_{i + 1}, \ldots, m_n $

oraz

$ m_1, \ldots,m_{i+1}, m_i, \ldots,m_n $

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

$ A = a_{1m_1} \ldots a_{im_i} a_{i+1m_{i+1}} \ldots a_{n m_n}= \prod_{k \ne i, i+1} a_{km_k} \cdot a_{im_i} a_{i+1 m_{i+1}} $

oraz

$ B = a_{1m_1} \ldots a_{im_{i+1}} a_{i+1m_i} \ldots a_{n m_n}= \prod_{k \ne i, i+1} a_{km_k} \cdot a_{im_{i+1}} a_{i+1 m_i}. $

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

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

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