1986 IMO Problems/Problem 6
Contents
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 parallel to one of the coordinate axes the difference (in absolute value) between the numbers of white and red points on is not greater than ?
Solution 1
I'll use a well-known result: if a connected graph has vertices of odd degree, then its edge set can be partitioned into paths, and if all its vertices have even degree, then it has an eulerian circuit.
We have a bipartite graph with bipartition here, constructed as follows: the horizontal lines which contain points from our set represent the vertices in , the vertical lines represent the vertices in , 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 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 vertices with odd degre, then we partition the edge set into 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 points. We will show there is a function for points.
If there exists a line , 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 , and consider . By inductive hypothesis there exists such a function for . Since contain even number of points, we have . Let be the line to , passing through . Let , where . Now for (with points) define as for , and , if , or or if . It indeed works as such a function for 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 . Let and be the two lines containing . Also . Consider , for this set , by the inductive hypothesis, there exists such a function . In , and contains odd number of points and if is a line different from and , then it contains even number of points. So . Therefore it is seen that
.
Since contain odd number of points, is either or . Wlog . Now for , (containing points) define as : , for and .
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]
See Also
1986 IMO (Problems) • Resources | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Last Question |
All IMO Problems and Solutions |