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 "2005 USAMO Problems/Problem 5"

m
m
Line 4: Line 4:
 
Prove that there exist at least two balancing lines.
 
Prove that there exist at least two balancing lines.
  
−
== Solutions ==
+
== Solution ==
  
 
Consider the convex hull of the the <math>2n</math> 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.
 
Consider the convex hull of the the <math>2n</math> 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.

Revision as of 18:04, 11 April 2013

Problem 5

Let $n$ be an integer greater than 1. Suppose $2n$ points are given in the plane, no three of which are collinear. Suppose $n$ of the given $2n$ points are colored blue and the other $n$ 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 $2n$ 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 $R_i$. Let $b_i$ and $r_i$ be the number of points encountered before $R_i$. Then $r_i=i-1$.

Define a sequence $f(i)=b_i-r_i$. Then $f(1)=b_i-(1-1)=b_i\geq0$ $f(n)=b_n-(n-1)=b_n-n+1\leq0$, because we can only encounter up to n-1 blue points. Thus, $f(i)$ goes from negative to positive as $i$ goes from 1 to $n$. We can also see that $f(i)$ can only increase by one for each change in i, so we know $f(i)$ must be 0 for some value of $i$, and so 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 $3>2$ balancing lines for the set of points when the convex hull is all the same color, and the statement is true as we desired.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_USAMO_Problems/Problem_5&oldid=52483"