## 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$.