An IMO problem

July 20, 2010

I spent this weekend working on and off a very interesting IMO problem – problem 6 from IMO 2006. You can find that here . It was a real hard nut and only led to a crushed ego :( . Let me first describe the problem and a result I managed to prove in this direction, which was however much weaker than the problem statement.

IMO 2006 Problem 6 : Assign to each side b of a convex polygon P the maximum area of a triangle that has b as a side and is contained in P. Show that the sum of the areas assigned to the sides of P is at least twice the area of P.

I managed to prove the following result.

Theorem: Assign to each side b of a convex polygon P the maximum area of a triangle that has b as a side and is contained in P. Then the sum of the areas assigned to the sides of P is at least \frac{3}{2} the area of P.

The proof is as follows. We prove first a small lemma.

Lemma 1 : Let P be a convex polygon with n \geq 4 sides. Then there is a quadrilateral or a triangle with vertices among the vertices of P that has area at least \frac{1}{2} the area of P.

Proof: Let the polygon have vertices A_1, A_2, \dots, A_n. Without loss of generality assume that A_1 A_k is the longest diagonal. The angles \angle A_k A_1 A_2, \angle A_k A_1 A_n, \angle A_1 A_k A_{k-1}, \angle A_1 A_k A_{k+1} are all less than \pi/2 since A_1 A_k is the longest diagonal. See the figure below for an example. For any vertex A_i denote by h(A_i) the distance from the line A_1 A_k. We will call the number h(A_i) the height of A_i.

If k = 2 or k = n then let A_q be the vertex with maximum height. By our earlier observation regarding the angles at vertices A_1, A_k with the line A_1 A_k, P is enclosed inside the rectangle with base A_1 A_k and height h(A_q). As such the area of the triangle A_1 A_k A_q is at least \frac{1}{2} the area of P.

If 2 < k < n consider the vertex A_p that has the maximum height among all vertices A_i, 1 < i < k and the vertex A_q that has maximum height among all vertices A_i, k < i \leq n. Clearly as before P is enclosed inside the rectangle R with a side parallel to A_1 A_k through A_p, A_q and the other sides through A_1 and A_k. Now

\text{area}(A_1 A_p A_k A_q) = \text{area}(A_1 A_p A_k) + \text{area}(A_1 A_k A_q) \geq \frac{1}{2} \text{area}(R)

We can now prove the theorem as follows.

Proof of Theorem: Let A_1 A_p A_k A_q be a maximum area quadrilateral whose vertices are also vertices of P. We will call this quadrilateral Q. Clearly \text{area}(Q) \geq \frac{1}{2} \text{area}(P) as we saw in the
previous lemma. The lemma actually showed that in few cases there
is actually a triangle T with vertices among those of P with area at least \frac{1}{2} of P. We will not deal with the case of a triangle here since it is similar but we remark that if there is such a triangle, the theorem actually gets stronger and we can in fact prove what was required in the IMO problem.

Consider the triangles in the following four sets

\left \{ A_1 A_2 A_q, A_2 A_3 A_q, \dots, A_{p-1} A_p A_q \right \}

\left \{ A_p A_{p+1} A_q, \dots, A_{k-1} A_k A_q \right \}

\left \{ A_k A_{k+1} A_p, \dots, A_{q-1} A_q A_p \right \}

\left \{ A_q A_{q+1} A_p, \dots, A_n A_1 A_p \right \}

The sum of the areas of the triangles is at most the sum of the numbers on the edges b of P. However, the sum of the areas is easily seen to be at least

\text{area}(P) + \text{area}(Q) \geq \frac{3}{2} \text{area}(P)

and we are done.

I found the solution to the IMO problem here and it is a real gem. It was a relief to see the solution!

Leave a Comment » | Problem Solving | Permalink
Posted by cstheory

Follow

Get every new post delivered to your Inbox.