Problem

Source: Junior Olympiad of Malaysia 2013 P3

Tags: combinatorics



The cells of an $n \times n$ table are filled with the numbers $1,2,\dots,n$ for the first row, $n+1,n+2,\dots,2n$ for the second, and so on until $n^2-n,n^2-n+1,\dots,n^2$ for the $n$-th row. Peter picks $n$ numbers from this table such that no two of them lie on the same row or column. Peter then calculates the sum $S$ of the numbers he has chosen. Prove that Peter always gets the same number for $S$, no matter how he chooses his $n$ numbers.