Difference between revisions of "2013 IMO Problems/Problem 2"

(Solution)
(Solution)
 
Line 9: Line 9:
 
==Solution==
 
==Solution==
  
Tip: don't overthink this one.
+
We can start off by imagining the points in their worst configuration.
 +
With some trials, we find <math>2013</math> lines to be the answer to the worst cases.
 +
We can assume the answer is <math>2013</math>. We will now prove it.
  
We can start off by imagining the points in their worst configuration.
 
With some trials, we find 2013 lines to be the answer to the worst cases.
 
We can assume the answer is 2013. We will now prove it.
 
  
We will prove that the minimum number of lines required for a "good" arrangement for a configuration consisting of u red points and v blue points, where u is even and v is odd and u - v = 1, is v.  
+
We will '''first''' prove that the sufficient number of lines required for a ''good'' arrangement for a configuration consisting of <math>u</math> red points and <math>v</math> blue points, where <math>u</math> is even and <math>v</math> is odd and <math>u - v = 1</math>, is <math>v</math>.  
  
 
Notice that the condition "no three points are co-linear" implies the following:  
 
Notice that the condition "no three points are co-linear" implies the following:  
 
No blue point will get in the way of the line between two red points and vice versa.  
 
No blue point will get in the way of the line between two red points and vice versa.  
What this means, is that for any two points A and B of the same color, we can draw two lines parallel to, and on different sides of the line AB, to form a region with only the points A and B in it.  
+
What this means, is that for any two points <math>A</math> and <math>B</math> of the same color, we can draw two lines parallel to, and on different sides of the line <math>AB</math>, to form a region with only the points <math>A</math> and <math>B</math> in it.  
  
Now consider a configuration consisting of u red points and v blue ones (u is even, v is odd, u>v).   
+
Now consider a configuration consisting of u red points and v blue ones (<math>u</math> is even, <math>v</math> is odd, <math>u>v</math>).   
Let the set of points S = {A1, A2, ... Ak} be the out-most points of the configuration, such that you could form a convex k-gon, A1A2A3...Ak, that has all of the other points within it.  
+
Let the set of points <math>S = \{A_1, A_2, ... A_k\}</math> be the out-most points of the configuration, such that you could form a convex k-gon, <math>A_1 A_2 A_3 ... A_k</math>, that has all of the other points within it.  
  
 
If the set S has at least one blue point, there can be a line that separates the plane into two regions: one only consisting of only a blue point, and one consisting of the rest. For the rest of the blue points, we can draw parallel lines as mentioned before to split them from the red points.
 
If the set S has at least one blue point, there can be a line that separates the plane into two regions: one only consisting of only a blue point, and one consisting of the rest. For the rest of the blue points, we can draw parallel lines as mentioned before to split them from the red points.
We end up with v lines.  
+
We end up with <math>v</math> lines.
 +
 
 +
If the set <math>S</math> has no blue points, there can be a line that divides the plane into two regions: one consisting of two red points, and one consisting of the rest. For the rest of the red points, we can draw parallel lines as mentioned before to split them from the blue points.
 +
We end up with <math>u-1 = v</math> lines.
 +
 
 +
'''Now''' we will show that there are configurations that can not be partitioned with less than <math>v</math> lines.
 +
 
 +
Consider the arrangement of these points on a circle so that between every two blue points there are at least one red point (on the circle).  
  
If the set S has no blue points, there can be a line that divides the plane into two regions: one consisting of two red points, and one consisting of the rest. For the rest of the red points, we can draw parallel lines as mentioned before to split them from the blue points.
+
There are no less than <math>2v</math> arcs of this circle, that has one end blue and other red (and no other colored points inside the arc) - one such arc on each side of each blue point.
We end up with u-1 = v lines.
+
For a line partitioning to be good, each of these arcs have to be crossed by at least one line, but one line can not cross more than <math>2</math> arcs on a circle - therefore, this configuration can not be partitioned with less than <math>v</math> lines!
  
Our proof is done, and we have our final answer: 2013.
+
Our proof is done, and we have our final answer: <math>2013</math>.
  
 
==See Also==
 
==See Also==
 
*[[2013 IMO]]
 
*[[2013 IMO]]

Latest revision as of 03:30, 18 June 2018

Problem

A configuration of $4027$ points in the plane is called Colombian if it consists of $2013$ red points and $2014$ blue points, and no three of the points of the configuration are collinear. By drawing some lines, the plane is divided into several regions. An arrangement of lines is good for a Colombian configuration if the following two conditions are satisfied:

  • no line passes through any point of the configuration;
  • no region contains points of both colours.

Find the least value of $k$ such that for any Colombian configuration of $4027$ points, there is a good arrangement of $k$ lines.

Solution

We can start off by imagining the points in their worst configuration. With some trials, we find $2013$ lines to be the answer to the worst cases. We can assume the answer is $2013$. We will now prove it.


We will first prove that the sufficient number of lines required for a good arrangement for a configuration consisting of $u$ red points and $v$ blue points, where $u$ is even and $v$ is odd and $u - v = 1$, is $v$.

Notice that the condition "no three points are co-linear" implies the following: No blue point will get in the way of the line between two red points and vice versa. What this means, is that for any two points $A$ and $B$ of the same color, we can draw two lines parallel to, and on different sides of the line $AB$, to form a region with only the points $A$ and $B$ in it.

Now consider a configuration consisting of u red points and v blue ones ($u$ is even, $v$ is odd, $u>v$). Let the set of points $S = \{A_1, A_2, ... A_k\}$ be the out-most points of the configuration, such that you could form a convex k-gon, $A_1 A_2 A_3 ... A_k$, that has all of the other points within it.

If the set S has at least one blue point, there can be a line that separates the plane into two regions: one only consisting of only a blue point, and one consisting of the rest. For the rest of the blue points, we can draw parallel lines as mentioned before to split them from the red points. We end up with $v$ lines.

If the set $S$ has no blue points, there can be a line that divides the plane into two regions: one consisting of two red points, and one consisting of the rest. For the rest of the red points, we can draw parallel lines as mentioned before to split them from the blue points. We end up with $u-1 = v$ lines.

Now we will show that there are configurations that can not be partitioned with less than $v$ lines.

Consider the arrangement of these points on a circle so that between every two blue points there are at least one red point (on the circle).

There are no less than $2v$ arcs of this circle, that has one end blue and other red (and no other colored points inside the arc) - one such arc on each side of each blue point. For a line partitioning to be good, each of these arcs have to be crossed by at least one line, but one line can not cross more than $2$ arcs on a circle - therefore, this configuration can not be partitioned with less than $v$ lines!

Our proof is done, and we have our final answer: $2013$.

See Also

Invalid username
Login to AoPS