Stop Drawing On the Checkerboard! Topic: Logic.

Problem: (2001 Putnam - B1) 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: Consider all the values of the red squares $ r_1, r_2, \ldots, r_{k} $ and all the values of the black squares $ b_1, b_2, \ldots, b_{l} $. For each square (of any color) $ a_i $, let

$ a_i = R(a_i)n+C(a_i) $,

where $ R(a_i)+1 $ and $ C(a_i) $ are the row and column of the square corresponding to $ a_i $. We want to show that

$ \displaystyle \sum r_i = \sum b_i $.

But we have

$ \displaystyle \sum r_i = \sum R(r_i)n + \sum C(r_i) $ and $ \displaystyle \sum b_i = \sum R(b_i)n + \sum C(b_i) $.

Since each row has half red and half black, we have

$ \displaystyle \sum R(r_i)n = \sum R(b_i)n $

for each row and consequently the whole board. Similarly, since each column has half red and half black, we have

$ \displaystyle \sum C(r_i) = \sum C(b_i) $

for each column and hence the whole board. Adding these two equalities together, we obtain

$ \displaystyle \sum r_i = \sum b_i $

as desired. QED.

--------------------

Comment: Not too hard intuitively, but slightly difficult to put down a rigorous proof; assigning variables can be a good way of going about solving word problems. It might simplify the problem down to some simple algebra, which is good.

--------------------

Practice Problem: Let $ n $ be a positive even integer. In how many ways can we fill an $ n \times n $ board with $ 1 $'s and $ -1 $'s such that the sum of each row and column is zero?