Friday, January 27, 2006

Big-gon. Topic: Pigeonhole Principle. Level: Olympiad.

Problem: (Olympiad Problem Solving MidTerm) At each of the vertices of a regular $100$–gon one of the numbers $1, 2, \ldots , 49$ is written. Prove
that there are $4$ vertices $A,B,C,D$ of this polygon such that

(a) $AB \parallel CD$, and
(b) if the numbers written at $A,B,C,D$ are $a, b, c, d$, respectively, then $a + b = c + d$.

Solution: Well looking at the numbers given, it's not terribly difficult to guess that it is a Pigeonhole problem (the $100$ and the $49$ are pretty good indicators). But what are the pigeons and the holes?

Consider the longest diagonals (connecting two opposite vertices). There are $50$ of these, conveniently enough. Label each of these diagonals with the absolute value of their difference. These differences range from $ 0 $ to $ 48 $ because the maximal difference is $ 49-1 = 48 $ and the minimal is clearly zero from the absolute value.

Now let the possible differences be the holes and the diagonals be the pigeons; since we have $49$ holes and $50$ pigeons, there are two diagonals with equal differences. Let $x,y$ be the endpoints of the first and $z,w$ the endpoints of the second.

We know that $ |x-y| = |z-w| $. Also note that $ x,y,z,w $ form a rectangle because it has two diagonals of equal length which bisect each other. Thus the opposite sides are parallel. If $ x-y = z-w $, we have $ x+w = z+y $, but those are opposite sides and hence parallel and we are done. If $ x-y = w-z $, we have $ x+z = w+y $, which again are opposite sides so we are done here, too. Hence the problem is solved. QED.


Comment: Took a bit to realize how to set up the pigeons and the holes, but it worked out nicely. It's good practice to do a lot of Pigeonhole problems because when you see one you have more experience in determining the pigeons and the holes.


Practice Problem: Generalize the problem to a $2n$-gon with the numbers $ 1,2,\ldots, n-1 $.

No comments:

Post a Comment