1986 IMO Problems/Problem 6

Problem

Given a finite set of points in the plane, each with integer coordinates, is it always possible to color the points red or white so that for any straight line $L$ parallel to one of the coordinate axes the difference (in absolute value) between the numbers of white and red points on $L$ is not greater than $1$ ?

Solution 1

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.

This solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [1]

Solution 2

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.

This solution was posted and copyrighted by Learner94. The original thread for this problem can be found here: [2]

1986 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last Question
All IMO Problems and Solutions

Page

Toolbox

Search

1986 IMO Problems/Problem 6

Contents

Problem

Solution 1

Solution 2

See Also