Question 2.6.27: The positive integers 1, 2, . . . , n² are placed in some fa......
The positive integers 1, 2, . . . , n² are placed in some fashion in the squares of an n × n table. As each number is placed in a square, the sum of the numbers already placed in the row and column containing that square is written on a blackboard. Give an arrangement of the numbers that minimizes the sum of the numbers written on the blackboard.
Rather than describe the arrangement, we demonstrate it for n = 4:
1 5 9 13
14 2 6 10
11 15 3 7
8 12 16 4
Note that the sum of the numbers written may also be computed as the product of each number with the number of empty spaces in its row and column at the time it was placed.
We now simply note that the contribution from rows is at least that of the minimal arrangement, and analogously for columns. This is because we end up multiplying n numbers by each of 0, 1, . . . , n − 1. By the rearrangement inequality, the total is minimizing by multiplying 1, . . . , n by n − 1, n + 1, . . . , 2n by n − 2, and so on.