Enough geometry already! Let’s switch gears and explore an interesting phenomenon in balanced grid coloring:

Problem: The numbers 1,2,…,100 are written in order in a \(10\times 10\) grid. Some grid cells are colored red, and the rest blue, in such a way that exactly half the cells in each row and each column are red (call this a balanced coloring). Show that the sum of the numbers in red cells equals the sum of the numbers in blue cells.

How can we understand this question? Notice that each row needs five red and five blue cells, but the values in each row do not need to balance. Indeed, the first row of the first example above is very skewed toward blue: \(\text{red}=1+2+3+4+5=15\) and \(\text{blue}=6+7+8+9+10=40\). In fact, every row in that example is very skewed to one side or the other! But the fact that every column also needs five red and five blue numbers somehow forces these skewed row sums to cancel each other out. This is essentially what the problem asks us to prove.

A (Not So Great) Start

Here’s one idea: let’s just test all the balanced grid colorings! There can’t be too many, right? Let’s start small. How many balanced \(2\times 2\) grid colorings are there? (Each row needs 1 red and 1 blue.) Just two: the first cell is either red or blue, and everything else is determined from there (cf. binary sudoku). And each of these has a red sum and a blue sum of 5, so we’ve verified the problem for \(2\times 2\) grids. What about \(4\times 4\)? With a little work, you can compute by hand that there are 90 balanced colorings of a \(4\times 4\) grid (try this!). That’s already a lot of cases to check. For \(10\times 10\) grids, it turns out that there are 6736218287430460752 balanced colorings! Maybe it’s time to look for a different method.

A Solution

Here’s a method that does work. Start with a zero in each grid cell; the red and blue sums are certainly equal (they’re both zero). Now we’ll modify the values one row or column at a time. If we add 1 to each cell in a column, then the red and blue sums each increase by 5 (because each column is balanced), so the sums remain equal. Do this once in the first column, twice in the second column, and so on, resulting in the middle grid below (which must therefore have equal red and blue sums):

Now modify the rows: add 10 to the second row, 20 to the third row, etc., finally ending up with the numbers 1,2,…,100 in order. Each step preserves the fact that the red and blue sums match, so we’re done! Notice that this argument works for any even grid size; 10 is not special here.

About This Problem

This problem appeared (with different phrasing) in the 2001 Putnam Competition, a very challenging mathematics competition for undergraduate students in the United States and Canada. This competition’s directories contain even more solutions and insights into this problem (Problem 2001 B1).