Constancy of the sum of numbers chosen from a square Let us consider the squares of $n \times n$ chessboard filled with the numbers $1$ to $n^2$ serially such that the first row contains number from $1$ to $n$  ,second row contains number from $n+1$ to $2n$ and so on.If now we choose numbers in $n$ squares with the property that there is exactly one from each row and exactly one from each column and add up the sum in the chosen squares prove that the sum obtained is always $\frac n2 (n^2+1)$
I tried checking out a few cases and noticed that the numbers deviate equally from the diagonal elements I.e. the sum obtained is equal to sum of diagonal elements. However I couldn't prove it formally.Any ideas?Thanks.
 A: The entry in row $r$ and column $c$ is $r + n c - n$.  The sum of the row numbers of the squares you picked is always $1 + 2 + \ldots + n = n(n+1)/2$, the sum of the column numbers is also $n (n+1)/2$, and the number of squares is $n$.  So the sum of the entries you picked is
$$ \frac{n (n+1)}{2} + n \frac{n (n+1)}{2} - n^2 = \frac{n^3+n}{2} $$
A: First we can start by proving that this number will always be the same, no matter which $n$ numbers we choose. 
Notice that if we start by choosing all numbers along the downhill diagonal, we will have $n$ numbers, exactly one in each row and column. Let us call this arrangement $D$. Any arrangement of $n$ numbers chosen in this way can be achieved by switching the columns of two of the chosen squares in $D$. But when the columns of two numbers are switched, if they have $k$ squares between them, one of the numbers will increase by $k+1$ and the other will decrease by $k+1$ when their columns are switched, leaving the sum of all of the numbers the same.
Now all that we have to do is find the sum of the values of $D$ in an $n$ by $n$ chessboard, which is easier to do. The first number on $D$ is $1$, and then comes $n+2$, then $2n+3$, and so on, so the sum of these numbers is 
$$\sum_{i=0}^{n-1} in+i+1$$
This sum is easily evaluated, and it turns out to be the formula that you have:
$$\frac{1}{2}n(n^2+1)$$
A: Let $a_i$ be the column of the chosen square in the $i$th row.
Show that the value of this square is $a_i+n(i-1)$, and then
evaluate the sum $\sum_{i=1}^n (a_i+n(i-1))$ using the fact that
$$ \sum_{i=1}^n a_i = \sum_{i=1}^n i = \frac{1}{2}n(n+1)$$ since $\{a_i\}=\{1,\dots,n\}$.
