Balanced Coloring
12 Sep 2008
Puzzle

Given k arbitrary points in a grid of size m by n, is it always possible to color them either red or black such that each row and each column is balanced? A row or column is said to be balanced if the difference in the number of red and black points in it is at most one.

Source

Heard from Adnan Aziz in 1996. He had heard it from a friend who had heard it from Edsger Dijkstra.

Solution

Thanks to Iman Hajirasouliha for sending me this elegant solution! Model the grid with a bipartite graph G[X, Y], a vertex in part X for each row and a vertex in part Y for each column. Add edges between xi and yj iff there is a point in the corresponding place. If G has a cycle (it must be an even cycle), we color the edges alternatively and remove those edges. When this procedure can no longer be applied, we must be left with a tree. At this point, we can solve the problem by induction on the number of edges as follows: remove e a leaf edge, color the remaining edges balanced, now look at the parent of that leaf and choose the right color for e to maintain the induction hypothesis.