2014 IMO Problems/Problem 6
A set of lines in the plane is in if no two are parallel and no three pass through the same point. A set of lines in general position cuts the plane into regions, some of which have finite are; we call these its . Prove that for all sufficiently large , in any set of lines in general position it is possible to colour at least of the lines blue in such a way that none of its finite regions has a completely blue boundary.
I was wondering if the problem seems a bit ambiguous. As there are n set of lines in consideration, with the constraint that no two are parallel and none of them are concurrent (constraints 1 and 2). Picking any three set of lines from set of n lines (nC3) will give a triangle formed by these lines because of the above constraints. This means if we color any more than 2 set of lines, at least 1 triangle is going to have all the three lines as blue. This sets the upper limit on the number of lines to be colored blue as 2 and not . Is this right?
Thanks and regards
I think this is because (correct me) if a triangle is blue on the perimeter, if there is a line cutting through it, the coloring turns valid.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
Call the intersections, well, points. Then each line will have points. We call 2 points (on a line) neighbors if there are no other points on the line segment joining those 2. Then each finite region has to be a convex polygon whose any pair of neighboring vertices are, well, neighbors. Now start by coloring any line blue, and all points are uncolored (neither red nor blue).
Suppose there is an uncolored line which does not pass through any red points. Color that line blue. Now consider each of the intersections that line makes with the other blue lines. For each intersection point of the 2 blue lines , color it blue (it was originally uncolored). Now consider the neighbors of on , call them on and on (if there is only 1 neighbor, let the other point be an uncolored dummy). If neither nor is blue, we colour them both red. Else if neither nor is blue, we colour them both red. Otherwise, we colour the uncolored ones (out of the 4 points) red. Anyway, we would have colored at most 2 points red. Once we have done this for all the intersection points, proceed back to the start of this paragraph until no such line exists.
Now to show it works. Suppose there is a finite region polygon with all blue boundaries (with ). Then all the points must be blue. Consider the first point colored blue, WLOG let it be . Suppose the previous line to be colored blue is . Then has to be colored blue before that, and has to be uncolored (otherwise will be colored blue first). So is uncolored. Then if is blue, will be colored red by our coloring algorithm. has to be uncolored and by our coloring algorithm at least one of will be colored red. Note that no blue line will pass through a red point. Thus there are no finite region with blue boundaries.
Now suppose lines are blue. By our algorithm, each blue point intersection will introduce at most 2 red points. Since we can't color any more lines blue, those red points will cover the remaining lines. Thus exact.
Note: this works for all , provided there is no mistake.
|2014 IMO (Problems) • Resources)|
|1 • 2 • 3 • 4 • 5 • 6||Followed by|
|All IMO Problems and Solutions|