Advanced book on Mathematics Olympiad

334 Methods of Proof

colored by a third color (Figure 46). The new diagonal dissects the polygon into two poly-
gons satisfying the property from the statement, and having fewer sides. The induction
hypothesis can be applied again, solving the problem.

r

r

b r

b

b

Figure 46

29.We prove the property by induction on the number of vertices. The base case is the
triangle, where there is nothing to prove.
Let us assume now that the property holds for polygons with fewer thannvertices
and prove it for a polygon withnvertices. The inductive step consists in finding one
interior diagonal.
We commence with an interior angle less thanπ(which does exist because the sum
of allnangles is(n− 2 )π). Let the polygon beA 1 A 2 ...An, with∠AnA 1 A 2 the chosen
interior angle. Rotate the ray|A 1 Antoward|A 1 A 2 continuously inside the angle as shown
in Figure 47. For each position of the ray, strictly betweenA 1 AnandA 1 A 2 , consider the
point on the polygon that is the closest toA 1. If for some position of the ray this point
is a vertex, then we have obtained a diagonal that divides the polygon into two polygons
with fewer sides. Otherwise,A 2 Anis the diagonal.

A

A

A

n

1

2

Figure 47

Dividing by the interior diagonal, we obtain two polygons with fewer vertices, which
by hypothesis can be divided into triangles. This completes the induction.

30.We induct on the number to be represented. For the base case, we have