Difference between revisions of "2014 IMO Problems/Problem 6"
(→Solution) |
m (→Problem) |
||
(4 intermediate revisions by 2 users 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== | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{{alternate solutions}} | {{alternate solutions}} | ||
Line 26: | Line 14: | ||
Now suppose <math>k</math> 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 <math>2\binom{k}{2}\geq n-k\implies k\geq \sqrt{n}</math> exact. | Now suppose <math>k</math> 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 <math>2\binom{k}{2}\geq n-k\implies k\geq \sqrt{n}</math> exact. | ||
− | Note: this works for all <math>n</math>, provided there is no mistake. | + | Note: this works for all <math>{n}\geq{2}</math>, provided there is no mistake. |
==See Also== | ==See Also== |
Latest revision as of 14: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 |