2005 USAMO Problems/Problem 5

From AoPSWiki

Problem 5

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.

Solutions

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 , 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 balancing lines for the set of points when the convex hull is all the same color, and the statement is true as we desired.