IMO 2003 SL C3

Origin: LIT | Category: Combinatorics

Problem

Let n \geq5 be a given integer. Determine the largest integer k for which there exists a polygon with n vertices (convex or not, with non-self-intersecting boundary) having k internal right angles.

Solution

Suppose that k of the angles of an n-gon are right. Since the other n −k angles are less than 360◦and the sum of the angles is (n−2)180◦, we have

the inequality k \cdot 90◦+ (n −k)360◦> (n −2)180◦, which is equivalent to k < 2n+4 . Since n and k are integers, it follows that k \leq / 2n

If n = 5, then / 2n

• 1 = 4, but if a pentagon has four right angles, the other angle is equal to 180◦, which is impossible. Hence for n = 5, k \leq3. It is easy to construct a pentagon with 3 right angles, e.g., as in the picture below. Now we shall show by induction that for n \geq6 there is an n-gon with / 2n
• 1 internal right angles. For n = 6, 7, 8 examples are presented in the picture. Assume that there is a (n−3)gon with  2(n−3)  +1 = / 2n −1 internal right angles. Then one of the internal angles, say \angleBAC, is not convex. Interchange the vertex A with four new vertices A1, A2, A3, A4 as shown in the picture such that \angleBA1A2 = \angleA3A4C = 90◦. n = 5 n = 6 n = 7 n = 8 C B A A1 A2 A3 A4 n −3 \ton