XXII OM - I - Problem 10

Given is a table with $ n $ rows and $ n $ columns. The number located in the $ m $-th column and $ k $-th row is equal to $ n(k - 1) + m $. How should $ n $ numbers be chosen, one from each row and each column, so that the product of these numbers is the largest?
Let's denote $ a_{k,m} = n (k - 1) + m $, where $ 1 \leq k, m \leq n $. Suppose we select the number in the column with number $ m_i $ from the $ i $-th row, where $ i = 1, 2, \ldots, n $. From the conditions of the problem, it follows that the sequence $ m_1, m_2, \ldots, m_n $ has distinct terms. Each such sequence corresponds to the product $ a_{1m_1} \cdot a_{2m_2} \cdot \ldots \cdot a_{nm_n} $.
We will prove that if the sequence $ m_1, m_2, \ldots, m_n $ is not decreasing, then the corresponding product is not the largest.
For example, let $ m_i < m_{i+1} $ for some $ i $. Consider the products $ A $ and $ B $ corresponding to the sequences:






and






(these sequences differ only in the terms with numbers $ i $ and $ i + 1 $). Therefore,






and






Let $ \displaystyle C= \prod_{k \ne i, i+1} a_{km_k} $ and using the definition of the numbers $ a_{km} $, we get:






Thus, $ B > A $, which means the product corresponding to the second sequence is greater than the product corresponding to the first. Therefore, we have proven that if the sequence $ m_1, m_2, \ldots, m_n $ is not decreasing, then the corresponding product is not the largest. Hence, the largest product corresponds to a decreasing sequence. Since from the numbers $ 1, 2, \ldots, n $, we can form only one $ n $-term decreasing sequence, namely the sequence $ n, n - 1, \ldots, 2, 1 $, the largest product is equal to $ a_{1n}a_{2n-1} \ldots a_{n1} = n(2n - 1) (3n - 2) (4n - 3) \ldots (n^2 - (n -1)) $.