Problem:
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:
We will show that every vertex of the convex hull of the set of given points lies on a balancing line.
Let be a vertex of the convex hull of the given points and assume, without loss of generality, that is red. Since is a vertex of the convex hull, there exists a line through such that all of the given points (except ) lie on the same side of . If we rotate about in the clockwise direction, we will encounter all of the blue points in some order. Denote the blue points by in the order in which they are encountered as is rotated clockwise about . For , let and be the numbers of blue points and red points, respectively, that are encountered before the point as is rotated (in particular, is not counted in and is never counted). Then
for , and
We show now that , for some . Define . Then and . Thus the sequence d_{1}, \ldots, d_
starts nonnegative and ends nonpositive. As grows, does not decrease, while always increases by exactly 1 . This means that the sequence can never decrease by more than 1 between consecutive terms. Indeed,
for . Since the integer-valued sequence starts nonnegative, ends nonpositive, and never decreases by more than 1 (so it never jumps over any integer value on the way down), it must attain the value 0 at some point, i.e., there exists some for which . For such an , we have and is a balancing line.
Since , the convex hull of the points has at least 3 vertices, and since each of the vertices of the convex hull lies on a balancing line, there must be at least two distinct balancing lines.
Notes. The main ingredient in the solution above is a discrete version of a "tortoise-and-hare" argument. Indeed, the tortoise crawls slowly but methodically and is at distance from the start at the moment , while the hare possibly jumps ahead at first , but eventually becomes lazy or distracted and finishes at most as far as the tortoise ). Since the tortoise does not skip any value and the hare never goes back towards the start, the tortoise must be even with the hare at some point.
We also note that a point not on the convex hull need not lie on any balancing line (for example, let and let the convex hull be a triangle).
One can show (with much more work) that there are always at least balancing lines; this is a theorem of J. Pach and R. Pinchasi (On the number of balanced lines, Discrete and Computational Geometry 25 (2001), 611-628). This is the best possible bound. Indeed, if consecutive vertices in a regular -gon are colored blue and the other are colored red, there are exactly balancing lines.
This problem was proposed by Kiran Kedlaya.
The problems on this page are the property of the MAA's American Mathematics Competitions