Advanced book on Mathematics Olympiad

342 Methods of Proof

47.Ann-gon has

(n

2

)

−n=^12 n(n− 3 )diagonals. Forn=21 this number is equal to

189. If through a point in the plane we draw parallels to these diagonals, 2× 189 = 378
     adjacent angles are formed. The angles sum up to 360◦, and thus one of them must be
     less than 1◦.

48.The geometric aspect of the problem is only apparent. If we number the vertices of the
polygon counterclockwise 1, 2 ,..., 2 n, thenP 1 ,P 2 ,...,P 2 nis just a permutation of these
numbers. We regard indices modulo 2n. ThenPiPi+ 1 is parallel toPjPj+ 1 if and only if
Pi−Pj≡Pj+ 1 −Pi+ 1 (mod 2n), that is, if and only ifPi+Pi+ 1 ≡Pj+Pj+ 1 (mod 2n).
Because

∑^2 n

i= 1

(Pi+Pi+ 1 )≡ 2

∑^2 n

i= 1

Pi≡ 2 n( 2 n− 1 )≡ 0 (mod 2n)

and

∑^2 n

i= 1

i=n( 2 n− 1 )≡n(mod 2n),

it follows thatPi+Pi+ 1 ,i= 1 , 2 ,..., 2 n, do not exhaust all residues modulo 2n.By
the pigeonhole principle there existi =jsuch thatPi+Pi+ 1 ≡Pj+Pj+ 1 (mod 2n).
Consequently, the sidesPiPi+ 1 andPjPj+ 1 are parallel, and the problem is solved.
(German Mathematical Olympiad, 1976)

49.LetCbe a circle inside the triangle formed by three noncollinear points inS. ThenC
is contained entirely inS. Setm=np+1 and consider a regular polygonA 1 A 2 ...Am
inscribed inC. By the pigeonhole principle, somenof its vertices are colored by the
same color. We have thus found a monochromaticn-gon. Now chooseαan irrational
multiple ofπ. The rotations ofA 1 A 2 ···Ambykα,k = 0 , 1 , 2 ,...,are all disjoint.
Each of them contains ann-gon with vertices colored byncolors. Only finitely many
incongruentn-gons can be formed with the vertices ofA 1 A 2 ···Am. So again by the
pigeonhole principle, infinitely many of the monochromaticn-gons are congruent. Of
course, they might have different colors. But the pigeonhole principle implies that one
color occurs infinitely many times. Hence the conclusion.
(Romanian Mathematical Olympiad, 1995)

50.This is an example in Ramsey theory (see Section 6.1.5) that applies the pigeonhole
principle. Pick two infinite families of lines,{Ai,i≥ 1 }, and{Bj,j≥ 1 }, such that
for anyiandj,AiandBjare orthogonal. Denote byMijthe point of intersection ofAi
andBj. By the pigeonhole principle, infinitely many of theM 1 j’s,j≥1, have the same
color. Keep only the linesBjcorresponding to these points, and delete all the others. So
again we have two families of lines, but such thatM 1 jare all of the same color; call this
colorc 1.