2005 USAMO Problems/Problem 5

Problem

(Kiran Kedlaya) 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$ . 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 $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.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

2005 USAMO (Problems • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2005 USAMO Problems/Problem 5

Problem

Solution

See Also