I'll use a well-known result: if a connected graph has $2k>0$ vertices of odd degree, then its edge set can be partitioned into $k$ paths, and if all its vertices have even degree, then it has an eulerian circuit. We have a bipartite graph with bipartition $A,B$ here, constructed as follows: the horizontal lines which contain points from our set represent the vertices in $A$, the vertical lines represent the vertices in $B$, and the point represent the edges between the vertices corresponding to the rows and columns which contain them. What we must prove is that we can color the edge set of a bipartite graph in two colors s.t. the difference between the number of red edges and white edges adjacent to each vertex is $\le 1$ in absolute value. It suffices to prove this for connected bipartite graphs, since then we can apply the result to each connected component of the graph. If all the vertices have even degree, then we can find an eulerian circuit. The graph is bipartite, so this circuit has an even number of edges, and we can thus color the edges in the circuit alternatively red and white so that two edges which are consecutive in the circuit have different colors. It's clear that this coloration satisfies the requirements. If, on the other hand, the graph has $2k>0$ vertices with odd degre, then we partition the edge set into $k$ paths, and in each path we color the edges alternatively red and white. Again, it's easy to verify the required properties of the coloration. P.S. I distinctly remember solving this before, but as far as I can remember, the argument was different.

A different proof: Let S be the smallest such set of points that cannot be colored according to the rules. S cannot contain a subset of the form {(a,b),(c,b),(c,d),(a,d)}: If S\{(a,b),(c,b),(c,d),(a,d)} can be colored then clearly S can be colored, and the former set is the smallest. S cannot contain a subset of the form {(a,b),(c,b),(c,d)}: If {(a,d)} U S\{(a,b),(c,b),(c,d)} can be colored, then S can be colored, and the former set is the smallest. Thus every point is either the only point in the column or the only point in the row, and it is easy to see that S can be colored. Contradiction.

Problem :Given a finite set $S$ , of points in the plane, each with integer coordinates, show that there is a function $f : P \to \left \{ -1, 1 \right \} $, so that for any straight line $L$ parallel to one of the coordinate axes, $\sum_{P \in L} f(P) \in \left \{ -1,0, 1 \right \}$ Solution : We induct on number of points. The small cases are easily checked. Let there exist such a function for $n$ points. We will show there is a function for $n+1$ points. If there exists a line $\ell$, parallel to any of the coordinate axes (from the next time, any line will be parallel to either of the coordinate axes, unless otherwise mentioned ), containing odd number of points, then choose a point $P_x \in \ell$, and consider $S \setminus P_x$. By inductive hypothesis there exists such a function $f : P \to \left \{ -1, 1 \right \}$ for $S \setminus P_x$. Since $P \in \ell, P \ne P_x$ contain even number of points, we have $\sum_{\substack{P \in \ell \\ P \ne P_x}} f(P) = 0$. Let $\ell '$ be the line $\perp$ to $\ell$, passing through $P_x$. Let $\sum _{\substack{P \in \ell ' \\ P \ne P_x}} f(P) = t $, where $t \in \left \{ -1,0 , 1 \right \} $. Now for $S$ (with $n+1 $ points) define $g$ as $g(P) = f(P)$ for $P \in S \setminus P_x$, and $g(P_x) = -t$, if $t \ne 0$, or $1$ or $-1$ if $t=0$. It indeed works as such a function for $n+1$ points. If the above is not the case, i.e. if all the lines contain even number (greater than zero) of points, pick up an arbitrary point $P_y \in S$. Let $\ell$ and $\ell '$ be the two lines containing $P_y$. Also $\ell \perp \ell '$. Consider $S \setminus P_y$, for this set , by the inductive hypothesis, there exists such a function $f$. In $S \setminus P_y$ , $\ell$ and $\ell '$ contains odd number of points and if $L$ is a line different from $\ell$ and $\ell '$, then it contains even number of points. So $\sum_{\substack{P \in L \\ L \ne \ell, \ell '}} f(P) = 0 $. Therefore it is seen that $\sum_{\substack{P \in \ell \\ P \ne P_y}} f(P) $ $= - \sum _{\substack{P \in S \\ P \notin \ell , \ell ' }} f(P)$ $ = \sum_{\substack{P \in \ell ' \\ P \ne P_y}} f(P) = t$. Since $\ell \setminus P_y$ contain odd number of points, $t$ is either $-1$ or $1$. Wlog $t = 1$. Now for $S$, (containing $n+1$ points) define $g$ as : $g(P) = f(P)$, for $P \in S \setminus P_y$ and $g(P_y) = -t$. So the induction is complete, and the statement is established.

Take the set with the smallest size that is not colorable like that. Any line must have en even number of points. Otherwise, take a line with an odd number of points, and forget about one of its points. Color the rest of the points, and you will find you can color the forgotten point accordingly. So, forget about one point, and color the other points. Suppose that in the vertical line of the point, color white "wins" (more whites than blacks). Then because the other vertical lines have an even number of points, color white wins in the whole set. So color white wins in the horizontal line containing the forgotten point. So we can color the forgotten point black and win. Done

So we consider the bipartite graph $R \cup C$, where $R$ denotes the row and $C$ denotes the columns. We want to show that for each vertex $V$, that the number of red edges incident to $V$ minus the number of white edges incident to $V$ is in the set $(-1, 0, 1)$ Now, connect two nodes with an edge if and only if there is a vertex lying at their intersection. The graph is bipartite, so all cycles are even. Now, if we color the edges in the even cycle alternately, we can preserve the difference. This means that we can remove even cycles arbitrarily, until the graph has no even cycles left. Now the graph may be disconnected, so we look at each connected component at a time. Because the connected components are each connected but have no even nor any odd cycles, they are all trees, so look at one tree at a time. I make the following claim. Now call red $1$ and white $-1$. We want to show that the sum of the edges incident to any vertex is always in $(-1, 0, 1)$. Call a vertex balanced if it satisfies this. We claim the following result: If there is a tree, and we weight at most one vertex negative one or one (in contrast to normally weighting it zero), we can weight each edge such that the result is satisfied. Proof: Take an arbitrary root to the tree, and it is clear that there is some way to balance the top vertex. Now, go down the graph and do the same weighting on all the subtrees, which are all disjoint, so we may do the problem inductively Hence, the result is proven. Now the desired result just comes from zero unbalanced vertices

A different proof: We consider the graph-theoretical formulation of this problem. First, we get rid of all cycles by coloring them alternately (this can be done as each cycle has even length). We consider the maximal path $\mathcal P$ in the graph. We color it alternately. Then we don't have to worry about vertices of $\mathcal P$ which are not its endpoints. Now endpoints of $\mathcal P$ must degree $1$ (otherwise, we could either find a longer path or a cycle). So we don't have to worry about the endpoints of $\mathcal P$ also. Doing this repeatedly, we are done. $\blacksquare$