IMO 1986 SL 9

Origin: GDR

Problem

Prove or disprove: Given a finite set of points with integer coordinates in the plane, it is possible to color some of these points red and the remaining ones white in such a way that for any straight line L parallel to one of the coordinate axes, the number of red colored points and the number of white colored points on L differ by at most 1.

Solution

We shall use induction on the number n of points. The case n = 1 is trivial. Let us suppose that the statement is true for all 1, 2, . . ., n −1, and that we are given a set T of n points. If there exists a point P \inT and a line l that is parallel to an axis and contains P and no other points of T , then by the inductive hypothesis we can color the set T \ {P} and then use a suitable color for P. Let us now suppose that whenever a line parallel to an axis contains a point of T , it contains another point of T . It follows that for an arbitrary point P0 \inT we can choose points P1, P2, . . . such that PkPk+1 is parallel to the x-axis for k even, and to the y-axis for k odd. We eventually come to a pair of integers (r, s) of the same parity, 0 \leqr < s, such that lines PrPr+1 and PsPs+1 coincide. Hence the closed polygonal line Pr+1Pr+2 . . . PsPr+1 is of even length. Thus we may color the points of this polygonal line alternately and then apply the inductive assumption for the rest of the set T . The induction is complete.

Second solution. Let P1, P2, . . . , Pk be the points lying on a line l parallel to an axis, going from left to right or from up to down. We draw segments joining P1 with P2, P3 with P4, and generally P2i−1 with P2i. Having this done for every such line l, we obtain a set of segments forming certain polygonal lines. If one of these polygonal lines is closed, then it must have an even number of vertices. Thus, we can color the vertices on each of the polygonal lines alternately (a point not lying on any of the polygonal lines may be colored arbitrarily). The obtained coloring satisfies the conditions.