Let $n$ be a positive integer. Assume that $n$ numbers are to be chosen from the table $\begin{array}{cccc}0 & 1 & \cdots & n-1\\ n & n+1 & \cdots & 2n-1\\ \vdots & \vdots & \ddots & \vdots\\(n-1)n & (n-1)n+1 & \cdots & n^2-1\end{array} $ with no two of them from the same row or the same column. Find the maximal value of the product of these $n$ numbers.
Problem
Source: 2013 Baltic Way, Problem 1
Tags: algebra unsolved, algebra
31.12.2013 02:07
Indexing the rows top-bottom from $0$ to $n-1$ and indexing the columns left-right from $0$ to $n-1$, the value at row $i$ and column $j$ is $a_{i,j} = ni + j$. Then $a_{i,j}a_{k,\ell} - a_{i,\ell}a_{k,j} = n(i-k)(\ell - j) > 0$ if either $i<k, j>\ell$ or $i>k, j<\ell$. This is enough to infer the maximum product is $\prod_{m=0}^{n-1} a_{m, n-m-1} = (n-1)^n \cdot n!$, of the elements on the second diagonal.
31.12.2013 03:49
mavropnevma wrote: This is enough to infer the maximum product is $\prod_{m=0}^{n-1} a_{m, n-m-1} = (n-1)^n \cdot n!$, of the elements on the second diagonal. Can you elaborate on how you made the inference?
05.01.2014 00:02
This is just because the elements are exact if the form $(m+1)(n-1)$
14.08.2021 21:16
Suppose we have numbers, $r_1n,r_2n+1,\ldots, r_nn+n-1$, where $r_1,r_2,\ldots r_n$ are different and $r_i\in [0,1,\ldots, n-1]$ and product attains its maximum at those values. Note that for any $1\leq i<j\leq n$, $$(r_in+i-1)\cdot (r_jn+j-1)\geq (r_jn+i-1)\cdot (r_in+j-1)\Longleftrightarrow r_i\geq r_j,$$thus $r_1>r_2>\ldots >r_n$, which means that $r_1=n-1,r_2=n-2,\ldots,r_n=0$. Hence, the maximum is $$(n-1)n\cdot (n-1)^2\cdot \ldots \cdot 2(n-1)\cdot n-1=(n-1)^nn!.$$