Colouring grid points (problem by Edgar Dijkstra)

 A problem due to Edgar Dijkstra.

You have an $N \times N$ grid of squares  and you have some number of squares on the grid marked as "special" squares. Show that you can colour each of the special squares red or blue, such for any row or column, the number of red squares is within one of the number of blue squares.

Scroll down for a solution.

.

.

.

.

.

This is a graph theory problem. 

You can view the grid as a bipartite graph, with the rows being the left set and the columns being the right set. There will be an edge between row $r$ and column $c$ iff the intersection of those is a special square. Thus it is enough to prove that we can colour the edges of a bipartite graph red or blue so that for each vertex the red degree is within one of the blue degree.

We prove by induction on the number of edges.  

Base cases are easy to verify.

If the graph is a tree (or a forest), pick any leaf node (vertex of degree one) and delete the edge that connects it to its tree. The rest can be coloured by induction. We can now add this edge back and colour it appropriately, without violating the constraint at the vertices where it is connected.

If the graph is not a tree/forest, it has a cycle. Since it is a bipartite graph, this cycle must be of even length. We alternately colour the edges of this cycle red and blue. Now colour the rest of the edges inductively.