Saudi Arabia Mathematical Competitions 2012

The answer is $n!\cdot (n-1{)}^n$. This is achievable by choosing the numbers $n-1,2(n-1),3(n-1),\dots ,n(n-1)$, which are at positions $(n,1),(n-1,2),(n-2,3),\dots ,(1,n)$. To show this is the best possible, we begin with a lemma.

Lemma. If $a<b<c<d$ are real numbers such that $a+d=b+c$, then $bc>ad$.

Proof. We have $(b-a)(c-a)>0$, which implies $$bc+(a-b-c)a>0.$$ Since $a-b-c=-d$, this simplifies to $bc>ad$ as desired. $\square$

Let $f(i,j)=(i-1)+n(j-1)$ be the number in row $i$ and column $j$. Suppose we have chosen the $n$ numbers $f(1,j_1),f(2,j_2),\dots ,f(n,j_n)$. If the $j_i$ sequence is strictly decreasing, then $j_i=n+1-i$ for all $i$ and we get a configuration in the first paragraph. Else there exists $k,m$ such that $k<m$ and $j_k<j_m$. Notice that $$f(k,j_k)<f(m,j_k)<f(k,j_m)<f(m,j_m).$$ Moreover, $$\begin{array}{rl}f(k,j_k)+f(m,j_m)& =f(m,j_k)+f(k,j_m)\\ & =(k+m-2)+n(j_k+j_m-2).\end{array}$$ So by the lemma, we have that $$f(k,j_k)f(m,j_m)<f(k,j_m)f(m,j_k).$$ Therefore we increase the product of the $n$ numbers by changing $f(k,j_k)$ and $f(m,j_m)$ to $f(k,j_m)$ and $f(m,j_k)$, so our original arrangement could not have been a maximum.