Number the cells in a 2n x 2n grid from 1 to 4n2, starting at the top left and moving left to right along each row, then continuing at the left of the next row down and so on. Colour half the cells black and half white, so that just half the cells in each row and half the cells in each column are black. Show that however this is done the sum of the black squares equals the sum of the white squares.
The numbers in row i+1 are each 2ni larger than the numbers in the same columns in row 1. So the sum of the black numbers in row i+1 is 2n2i higher than the sum of the corresponding numbers in row 1. So the sum of all the black numbers is 2n2(1 + 2 + ... + 2n-1) higher than the sum where we count each number in the first row n times (there are n black numbers in each column). The same argument gives the same result for the white numbers, so the two sums are equal.
62nd Putnam 2001
© John Scholes
16 Dec 2001