2008 OIM Problems/Problem 1

Problem

Numbers were distributed on a board, such that in each box there is a different number. For each row and each column of the board, the difference between the largest and smallest of its elements is calculated. Let be the sum of the 4016 numbers obtained. Determine the largest possible value of .

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

We claim that the largest possible is . First, we show that such an arrangement is possible:

Begin at the bottom-left corner and place a . Continue along the board's diagonal placing a number one greater than the previous number. Then, place a at the top-left corner, and continue along this diagonal, at each box placing a number one less than the previous number. By construction, every number just described is the smallest/largest in both its row and its column, so each is counted twice; thus, here is: $$\begin{array}{rl}S& =2({2008}^2+({2008}^2-1)+\dots +({2008}^2-2007))-2(1+2+\dots +2008)\\ & =2(({2008}^2-2008)+({2008}^2-1-2007)+({2008}^2-2-2006)+\dots +({2008}^2-2007-1))\\ & =2(2008\cdot ({2008}^2-2008))\\ & =2\cdot 2008\cdot 2008\cdot 2007\\ & =4014\cdot {2008}^2\end{array}$$ Since each number can only be the smallest in two differences (that of its row and column), and since the subtracted numbers are the smallest possible integers and the added numbers are the largest possible integers, we are done.

~ eevee9406

See also

OIM Problems and Solutions