Solution combinatoric problem (Shortlist Problem no.2)
International mathematic Olympiad 2013
Problem 2 :
In the plane, 2013 red points and 2014 blue points are marked so that no three of the marked points are collinear. One needs to draw k lines not passing through the marked points and dividing the plane into several regions. The goal is to do it in such a way that no region contains points of both colors. Find the minimal value of k such that the goal is attainable for every possible configuration of 4027 points.
Answer. k = 2013.
Firstly, let us present an example showing that . Mark 2013 red and 2013 blue points on some circle alternately, and mark one more blue point somewhere in the plane. The circle is thus split into 4026 arcs, each arc having endpoints of different colors. Thus, if the goal is reached, then each arc should intersect some of the drawn lines. Since any line contains at most two points of the circle, one needs at least 4026 / 2 = 2013 lines.
It remains to prove that one can reach the goal using 2013 lines. First of all, let us mention that for every two points A and B having the same color, one can draw two lines separating these points from all other ones. Namely, it suffices to take two lines parallel to AB and lying on different sides of AB sufficiently close to it: the only two points between these lines will be A and B.
Now, let P be the convex hull of all marked points. Two cases are possible.
Case 1. Assume that P has a red vertex A. Then one may draw a line separating A from all the other points, pair up the other 2012 red points into 1006 pairs, and separate each pair from the other points by two lines. Thus, 2013 lines will be used.
Case 2. Assume now that all the vertices of P are blue. Consider any two consecutive vertices of P, say A and B. One may separate these two points from the others by a line parallel to AB. Then, as in the previous case, one pairs up all the other 2012 blue points into 1006 pairs, and separates each pair from the other points by two lines. Again, 2013 lines will be used.
Also Read : Combinatoric shortlist problem in IMO 2013