736 Combinatorics and Probability
842.We examine separately the casesn= 3 , 4 ,5. A triangle can have at most one right
angle, a quadrilateral four, and a pentagon three (if four angles of the pentagon were
right, the fifth would have to be equal to 180◦).
Let us consider ann-gon withn≥6 havingkinternal right angles. Because the other
n−kangles are less than 360◦and because the sum of all angles is(n− 2 )· 180 ◦, the
following inequality holds:
(n−k)· 360 ◦+k· 90 ◦>(n− 2 )· 180 ◦.This readily implies thatk<^2 n 3 +^4 , and sincekandnare integers,k≤^23 n+1.
We will prove by induction onnthat this upper bound can be reached. The base cases
n= 6 , 7 ,8 are shown in Figure 95.
Figure 95We assume that the construction is done fornand prove that it can be done forn+3.
For our method to work, we assume in addition that at least one internal angle is greater
than 180◦. This is the case with the polygons from Figure 95. For the inductive step
we replace the internal angle greater than 180◦as shown in Figure 96. This increases
the angles by 3 and the right angles by 2. The new figure still has an internal angle
greater than 180◦, so the induction works. This construction proves that the bound can
be reached.
Figure 96(short list of the 44th International Mathematical Olympiad, 2003)843.It seems that the situation is complicated by successive colorings. But it is not!
Observe that each time the moving circle passes through the original position, a new
point will be colored. But this point will color the same points on the fixed circle. In
short, only the first colored point on one circle contributes to newly colored points on the
other; all other colored points follow in its footsteps. So there will be as many colored
points on the small circle as there are points of coordinate 2πk,kan integer, on the
segment[ 0 , 200 π
√
2 ]. Their number is