Balanced Coloring


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.


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


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.

Previous Puzzle: Empty the Bucket

Three buckets have marbles. You are allowed to double the number of marbles in a bucket by borrowing from one of the other two buckets. Prove that it is possible to produce an empty bucket with a series of such operations.

Next Puzzle: Horses on Auction

You are the chief guest at an auction, where an unknown number of horses will be revealed and auctioned, one after the other, randomly permuted. You are a connoiseur of horses, and can judge whether one horse is 'better' than another. Being the chief guest, you have a one-time privilege of selecting a horse, after it is revealed, but before it gets auctioned off. You get to keep this horse for yourself. Your objective is to maximize the probability of selecting the best horse. One strategy is to pick the first horse. Can you do any better?

12 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.