Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2014 IMO Problems/Problem 6"

(Created page with "==Problem== A set of lines in the plane is in \textit{general position} if no two are parallel and no three pass through the same point. A set of lines in general position cuts t...")
 
m (→‎Problem)
 
(9 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
A set of lines in the plane is in \textit{general position} 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 \textit{finite regions}. 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.
+
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}}
 +
 +
Call the <math>\binom{n}{2}</math> intersections, well, points. Then each line will have <math>n-1</math> 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 <math>X</math> of the 2 blue lines <math>l_1,l_2</math>, color it blue (it was originally uncolored). Now consider the neighbors of <math>X</math> on <math>l_1,l_2</math>, call them <math>A_1,A_2</math> on <math>l_1</math> and <math>B_1,B_2</math> on <math>l_2</math> (if there is only 1 neighbor, let the other point be an uncolored dummy). If neither <math>A_1</math> nor <math>A_2</math> is blue, we colour them both red. Else if neither <math>B_1</math> nor <math>B_2</math> 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 <math>P_1...P_m</math> with all blue boundaries (with <math>P_{m+1}=P_1</math>). Then all the points must be blue. Consider the first point colored blue, WLOG let it be <math>P_2</math>. Suppose the previous line to be colored blue is <math>P_1P_2</math>. Then <math>P_2P_3</math> has to be colored blue before that, and <math>P_3P_4</math> has to be uncolored (otherwise <math>P_3</math> will be colored blue first). So <math>P_3</math> is uncolored. Then if <math>P_1</math> is blue, <math>P_3</math> will be colored red by our coloring algorithm. <math>P_1</math> has to be uncolored and by our coloring algorithm at least one of <math>P_1,P_3</math> will be colored red. Note that no blue line will pass through a red point. Thus there are no finite region with blue boundaries.
  
−
{{alternate solutions}}
+
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}\geq{2}</math>, provided there is no mistake.
  
 
==See Also==
 
==See Also==

Latest revision as of 13:50, 27 September 2020

Problem

A set of lines in the plane is in $\textit{general position}$ 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 $\textit{finite regions}$. Prove that for all sufficiently large $n$, in any set of $n$ lines in general position it is possible to colour at least $\sqrt{n}$ 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 $\binom{n}{2}$ intersections, well, points. Then each line will have $n-1$ 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 $X$ of the 2 blue lines $l_1,l_2$, color it blue (it was originally uncolored). Now consider the neighbors of $X$ on $l_1,l_2$, call them $A_1,A_2$ on $l_1$ and $B_1,B_2$ on $l_2$ (if there is only 1 neighbor, let the other point be an uncolored dummy). If neither $A_1$ nor $A_2$ is blue, we colour them both red. Else if neither $B_1$ nor $B_2$ 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 $P_1...P_m$ with all blue boundaries (with $P_{m+1}=P_1$). Then all the points must be blue. Consider the first point colored blue, WLOG let it be $P_2$. Suppose the previous line to be colored blue is $P_1P_2$. Then $P_2P_3$ has to be colored blue before that, and $P_3P_4$ has to be uncolored (otherwise $P_3$ will be colored blue first). So $P_3$ is uncolored. Then if $P_1$ is blue, $P_3$ will be colored red by our coloring algorithm. $P_1$ has to be uncolored and by our coloring algorithm at least one of $P_1,P_3$ 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 $k$ 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 $2\binom{k}{2}\geq n-k\implies k\geq \sqrt{n}$ exact.

Note: this works for all ${n}\geq{2}$, 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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_IMO_Problems/Problem_6&oldid=134175"