Difference between revisions of "2014 IMO Problems/Problem 6"
(→Solution) |
m (→Problem) |
||
| (2 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
| − | A set of lines in the plane is in <math>\textit{general position}</math> 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 | + | A set of lines in the plane is in <math>\textit{general position}</math> 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 area; we call these its <math>\textit{finite regions}</math>. Prove that for all sufficiently large <math>n</math>, in any set of <math>n</math> lines in general position it is possible to colour at least <math>\sqrt{n}</math> of the lines blue in such a way that none of its finite regions has a completely blue boundary. |
==Solution== | ==Solution== | ||
Latest revision as of 13:50, 27 September 2020
Problem
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 area; 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.
Solution
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.
See Also
| 2014 IMO (Problems) • Resources | ||
| Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
| All IMO Problems and Solutions | ||
