Saturday, March 11, 2006

Back To The Coloring Books. Topic: Combinatorial Geometry. Level: Olympiad.

Problem: (1991 APMO - #2) Suppose there are $997$ points given in a plane. If every two points are joined by a line segment with its midpoint coloured in red, show that there are at least $1991$ red points in the plane. Can you find a special case with exactly $1991$ red points?

Solution: We will prove a generalization - that given any set of $ n $ points in a plane, there are at least $ 2n-3 $ distinct midpoints. We proceed by induction.

Base Case - $ n = 2 $. We have $ 2(2)-3 = 1 $ midpoint.

Induction Step - Consider one of the vertices of the convex hull of the $ k+1 $ points. Call it $ P $. Let $ C $ be the convex hull of the other $ n $ points. By our inductive hypothesis, there exist at least $ 2k-3 $ distinct midpoints in $ C $ (since any midpoint has to be inside the convex hull).

Then take the vertex of $ C $ closest to $ P $ and call it $ X $. Segment $ XP $ must be outside of the convex hull (or $ X $ would not be the closest vertex). Hence the midpoint of $ XP $ is outside of $ C $ and is distinct from any of the existing midpoints. Let $ Y $ and $ Z $ be the vertices of $ C $ consecutive with $ X $. Since $ \angle YXP+\angle ZXP < 360 $ (assume $ X, Y, Z $ not collinear and the angle outside of the convex hull is taken), one of the two is less than $ 180 $.

WLOG, assume $ \angle YXP < 180 $. Then $YP $ is not inside $ C $ either because $ \angle YXP < 180 < \angle YXZ $. Hence there exists a second midpoint outside of the convex hull and distinct from the first.

If $ C $ is a segment, take $ X, Y $ the two closest points in $ C $ to $ P $ such that $ XP < YP $. Clearly the midpoint of $ XP $ is outside of $ C $ and the midpoint of $ YP $ must lie between $ Y $ and $ P $. But then the midpoint of any two other points must be further from $ P $ than the midpoint of $ YP $, so it is distinct as well.

Therefore we have at least $ 2k-3+2 = 2(k+1)-3 $ distinct midpoints (red points), completing the induction.

Letting $ n = 997 $, we find that there must exist at least $ 2(997)-3 = 1991 $ red points, as desired.

Picking the points $ (0,0); (2,0); \ldots; (1992,0) $ gives us the midpoints $ (1,0); (2,0); \ldots; (1991,0) $ of which there are exactly $ 1991 $ of. QED.

--------------------

Comment: Combinatorial geometry is probably one of the most interesting and least-known areas of mathematics (to high school students). It showed up on last year's USAMO and most people were baffled that standard techniques didn't work (induction, pigeonhole, extremal, etc.). The idea of the convex hull is very powerful and generates many interesting results.

--------------------

Practice Problem: (2005 USAMO - #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.

1 comment:

  1. Oh, I fixed the closed form for second-order recurrences. It works for fibonacci now, but it's pretty ugly (cancels out nicely in the Fibonacci case, a_0 = a_1 = r + s = 1:

    a_k = 1 / (r-s) * ( r^k (a_1 - sa_0) + s^k(a_1 - ra_0))

    ReplyDelete