Putnam 2001, Problem B-1

Let $n$ be an even positive integer. Write the numbers $1, 2, \ldots, n^2$ in the squares of an $n \times n$ grid so that the $k$-th row, from left to right, is
$$(k-1)n+1, (k-1)n+2, \ldots, (k-1)n+n.$$
Color the squares of the grid so that half of the squares in each row and in each column are red and the other half are black (a checkerboard coloring is one possibility). Prove that for each coloring, the sum of the numbers on the red squares is equal to the sum of the numbers on the black squares.

Solution:
Let $R$ (resp. $B$) denote the set of red (resp. black) squares in such a coloring, and for $s \in R \cup B$, let $f(s)n + g(s) + 1$ denote the number written in square $s$, where $0 \leq f(s),g(s) \leq n-1$. Then it is clear that the value of $f(s)$ depends only on the row of $s$, while the value of $g(s)$ depends only on the column of $s$. Since every row contains exactly $n/2$ elements of $R$ and $n/2$ elements of $B$,
$$\sum_{s \in R} f(s) = \sum_{s \in B} f(s).$$

Similarly, because every column contains exactly $n/2$ elements of $R$ and $n/2$ elements of $B$,
$$\sum_{s \in R} g(s) = \sum_{s \in B} g(s).$$

It follows that
$$\sum_{s \in R} f(s)n + g(s) + 1 = \sum_{s \in B} f(s)n + g(s) + 1,$$

as desired.

Note: Richard Stanley points out a theorem of Ryser (see Ryser, Combinatorial Mathematics, Theorem 3.1) that can also be applied. Namely, if $A$ and $B$ are 0-1 matrices with the same row and column sums, then there is a sequence of operations on $2 \times 2$ matrices of the form
$$\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \to \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$$

or vice versa, which transforms $A$ into $B$. If we identify 0 and 1 with red and black, then the given coloring and the checkerboard coloring both satisfy the sum condition. Since the desired result is clearly true for the checkerboard coloring, and performing the matrix operations does not affect this, the desired result follows in general.