Difference between revisions of "2005 USAMO Problems/Problem 5"
Alexlikemath (talk | contribs) m |
Alexlikemath (talk | contribs) |
||
| Line 13: | Line 13: | ||
Define a sequence <math>f(i)=b_i-r_i</math>. Then <math>f(1)=b_i-(1-1)=b_i\geq0</math> | Define a sequence <math>f(i)=b_i-r_i</math>. Then <math>f(1)=b_i-(1-1)=b_i\geq0</math> | ||
<math>f(n)=b_n-(n-1)=b_n-n+1\leq0</math>, because we can only encounter up to n-1 blue points. | <math>f(n)=b_n-(n-1)=b_n-n+1\leq0</math>, because we can only encounter up to n-1 blue points. | ||
| − | Thus, <math>f(i)</math> goes from negative to positive as <math>i</math> goes from 1 to <math>n</math>. We can also see that <math>f(i)</math> can only increase by one for each change in i, so we know <math>f(i)</math> must be 0 for some value of <math>i</math>. Take the first f(i) where f(i) = 0. Since f(i-1) must have been positive, the ith point must have been red. Thus there is a balancing line for every point on the convex hull. Since a polygon must have at least 3 vertices, there must be at least <math>3>2</math> balancing lines for the set of points when the convex hull is all the same color, and the statement is true as we desired. | + | Thus, <math>f(i)</math> goes from negative to positive as <math>i</math> goes from 1 to <math>n</math>. We can also see that <math>f(i)</math> can only increase by one for each change in i, so we know <math>f(i)</math> must be 0 for some value of <math>i</math>. Take the first <math>f(i)</math> where <math>f(i) = 0</math>. Since <math>f(i-1)</math> must have been positive, the ith point must have been red. Thus there is a balancing line for every point on the convex hull. Since a polygon must have at least 3 vertices, there must be at least <math>3>2</math> balancing lines for the set of points when the convex hull is all the same color, and the statement is true as we desired. |
{{alternate solutions}} | {{alternate solutions}} | ||
Revision as of 23:05, 3 August 2020
Problem
(Kiran Kedlaya) Let 
be an integer greater than 1. Suppose 
points are given in the plane, no three of which are collinear. Suppose of the given points are colored blue and the other colored red. A line in the plane is called a balancing line if it passes through one blue and one red point and, for each side of the line, the number of blue points on that side is equal to the number of red points on the same side.
Prove that there exist at least two balancing lines.
Solution
Consider the convex hull of the the points, or the points that would form the largest convex polygon. If the points in the convex hull contain both red and blue points, then there must be at least 2 edges of the graph of the convex hull such that the edge connects a blue and a red point. Drawing a line through those points would give a balancing line, as we have n-1 blue points and n-1 red points on one side, and 0 points on the other.
Therefore it suffices to show that there exist at least 2 balancing lines when the convex hull is colored all the same color.
Pick a random point on the convex hull, and without loss of generality we can say it is blue (if there are no red we can change all the colors, and end up with an equivalent setup). Consider a line going through it and not any other points. As we rotate the line clockwise, we encounter the red points in some order. Let the ith point encountered be 
. Let 
and 
be the number of points encountered before . Then 
.
Define a sequence 
. Then 
, because we can only encounter up to n-1 blue points.
Thus, 
goes from negative to positive as 
goes from 1 to . We can also see that can only increase by one for each change in i, so we know must be 0 for some value of . Take the first where 
. Since 
must have been positive, the ith point must have been red. Thus there is a balancing line for every point on the convex hull. Since a polygon must have at least 3 vertices, there must be at least 
balancing lines for the set of points when the convex hull is all the same color, and the statement is true as we desired.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See Also
| 2005 USAMO (Problems • Resources) | ||
| Preceded by Problem 4 |
Followed by Problem 6 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAMO Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
