IMO 2006 Shortlisted Problems

Lemma. Every convex $(2n)$-gon, of area $S$, has a side and a vertex that jointly span a triangle of area not less than $S/n$.

Proof. By main diagonals of the $(2n)$-gon we shall mean those which partition the $(2n)$-gon into two polygons with equally many sides. For any side $b$ of the $(2n)$-gon denote by ${\Delta }_b$ the triangle $ABP$ where $A,B$ are the endpoints of $b$ and $P$ is the intersection point of the main diagonals $A{A}^{\prime },B{B}^{\prime }$. We claim that the union of triangles ${\Delta }_b$, taken over all sides, covers the whole polygon.

To show this, choose any side $AB$ and consider the main diagonal $A{A}^{\prime }$ as a directed segment. Let $X$ be any point in the polygon, not on any main diagonal. For definiteness, let $X$ lie on the left side of the ray $A{A}^{\prime }$. Consider the sequence of main diagonals $A{A}^{\prime },B{B}^{\prime },C{C}^{\prime },\dots$, where $A,B,C,\dots$ are consecutive vertices, situated right to $A{A}^{\prime }$. The $n$-th item in this sequence is the diagonal $A^{\prime }A$ (i.e. $A{A}^{\prime }$ reversed), having $X$ on its right side. So there are two successive vertices $K,L$ in the sequence $A,B,C,\dots$ before $A^{\prime }$ such that $X$ still lies to the left of $K{K}^{\prime }$ but to the right of $L{L}^{\prime }$. And this means that $X$ is in the triangle ${\Delta }_{{\ell }^{\prime }}$, ${\ell }^{\prime }=K^{\prime }{L}^{\prime }$. Analogous reasoning applies to points $X$ on the right of $A{A}^{\prime }$ (points lying on main diagonals can be safely ignored). Thus indeed the triangles ${\Delta }_b$ jointly cover the whole polygon.

The sum of their areas is no less than $S$. So we can find two opposite sides, say $b=AB$ and $b^{\prime }=A^{\prime }{B}^{\prime }$ (with $A{A}^{\prime },B{B}^{\prime }$ main diagonals) such that $[{\Delta }_b]+[{\Delta }_{b^{\prime }}]\ge S/n$, where $[\cdots ]$ stands for the area of a region. Let $A{A}^{\prime },B{B}^{\prime }$ intersect at $P$; assume without loss of generality that $PB\ge P{B}^{\prime }$. Then $$[AB{A}^{\prime }]=[ABP]+[PB{A}^{\prime }]\ge [ABP]+[P{A}^{\prime }{B}^{\prime }]=[{\Delta }_b]+[{\Delta }_{b^{\prime }}]\ge S/n,$$ proving the lemma. $\square$

Now, let $\mathcal{P}$ be any convex polygon, of area $S$, with $m$ sides $a_1,\dots ,a_m$. Let $S_i$ be the area of the greatest triangle in $\mathcal{P}$ with side $a_i$. Suppose, contrary to the assertion, that $$\sum _{i=1}^m\frac{S_i}{S}<2.$$ Then there exist rational numbers $q_1,\dots ,q_m$ such that $\sum q_i=2$ and $q_i>S_i/S$ for each $i$.

Let $n$ be a common denominator of the $m$ fractions $q_1,\dots ,q_m$. Write $q_i=k_i/n$; so $\sum k_i=2n$. Partition each side $a_i$ of $\mathcal{P}$ into $k_i$ equal segments, creating a convex $(2n)$-gon of area $S$ (with some angles of size $180^{\circ }$), to which we apply the lemma. Accordingly, this refined polygon has a side $b$ and a vertex $H$ spanning a triangle $T$ of area $[T]\ge S/n$. If $b$ is a piece of a side $a_i$ of $\mathcal{P}$, then the triangle $W$ with base $a_i$ and summit $H$ has area $$[W]=k_i\cdot [T]\ge k_i\cdot S/n=q_i\cdot S>S_i,$$ in contradiction with the definition of $S_i$. This ends the proof.

---

Alternative solution.

As in the first solution, we allow again angles of size $180^{\circ }$ at some vertices of the convex polygons considered.

To each convex $n$-gon $\mathcal{P}=A_1{A}_2\dots A_n$ we assign a centrally symmetric convex $(2n)$-gon $\mathcal{Q}$ with side vectors $\pm \overrightarrow{A_i{A}_{i+1}},1\le i\le n$. The construction is as follows. Attach the $2n$ vectors $\pm \overrightarrow{A_i{A}_{i+1}}$ at a common origin and label them $\overrightarrow{{\mathbf{b}}_1},\overrightarrow{{\mathbf{b}}_2},\dots ,\overrightarrow{{\mathbf{b}}_{2n}}$ in counterclockwise direction; the choice of the first vector $\overrightarrow{{\mathbf{b}}_1}$ is irrelevant. The order of labelling is well-defined if $\mathcal{P}$ has neither parallel sides nor angles equal to $180^{\circ }$. Otherwise several collinear vectors with the same direction are labelled consecutively $\overrightarrow{{\mathbf{b}}_j},\overrightarrow{{\mathbf{b}}_{j+1}},\dots ,\overrightarrow{{\mathbf{b}}_{j+r}}$. One can assume that in such cases the respective opposite vectors occur in the order $-{\overrightarrow{{\mathbf{b}}_j}}^{\prime },-\overrightarrow{{\mathbf{b}}_{j+1}},\dots ,-\overrightarrow{{\mathbf{b}}_{j+r}}$, ensuring that $\overrightarrow{{\mathbf{b}}_{j+n}}=-\overrightarrow{{\mathbf{b}}_j}$ for $j=1,\dots ,2n$. Indices are taken cyclically here and in similar situations below.

Choose points $B_1,B_2,\dots ,B_{2n}$ satisfying $\overrightarrow{B_j{B}_{j+1}}=\overrightarrow{{\mathbf{b}}_j}$ for $j=1,\dots ,2n$. The polygonal line $\mathcal{Q}=B_1{B}_2\dots B_{2n}$ is closed, since ${\sum }_{j=1}^{2n}\overrightarrow{{\mathbf{b}}_j}=\overrightarrow{0}$. Moreover, $\mathcal{Q}$ is a convex $(2n)$-gon due to the arrangement of the vectors $\overrightarrow{{\mathbf{b}}_j}$, possibly with $180^{\circ }$-angles. The side vectors of $\mathcal{Q}$ are $\pm \overrightarrow{A_i{A}_{i+1}}$, $1\le i\le n$. So in particular $\mathcal{Q}$ is centrally symmetric, because it contains as side vectors $\overrightarrow{A_i{A}_{i+1}}$ and $-\overrightarrow{A_i{A}_{i+1}}$ for each $i=1,\dots ,n$. Note that $B_j{B}_{j+1}$ and $B_{j+n}{B}_{j+n+1}$ are opposite sides of $\mathcal{Q}$, $1\le j\le n$. We call $\mathcal{Q}$ the associate of $\mathcal{P}$.

Let $S_i$ be the maximum area of a triangle with side $A_i{A}_{i+1}$ in $\mathcal{P}$, $1\le i\le n$. We prove that $$\left[B_1{B}_2\dots B_{2n}\right]=2\sum _{i=1}^n{S}_i\text{\hspace{1em}(1)}$$ and $$\left[B_1{B}_2\dots B_{2n}\right]\ge 4\left[A_1{A}_2\dots A_n\right]\text{\hspace{1em}(2)}$$ It is clear that (1) and (2) imply the conclusion of the original problem.

Lemma. For a side $A_i{A}_{i+1}$ of $\mathcal{P}$, let $h_i$ be the maximum distance from a point of $\mathcal{P}$ to line $A_i{A}_{i+1}$, $i=1,\dots ,n$. Denote by $B_j{B}_{j+1}$ the side of $\mathcal{Q}$ such that $\overrightarrow{A_i{A}_{i+1}}=\overrightarrow{B_j{B}_{j+1}}$. Then the distance between $B_j{B}_{j+1}$ and its opposite side in $\mathcal{Q}$ is equal to $2h_i$.

Proof. Choose a vertex $A_k$ of $\mathcal{P}$ at distance $h_i$ from line $A_i{A}_{i+1}$. Let $\mathbf{u}$ be the unit vector perpendicular to $A_i{A}_{i+1}$ and pointing inside $\mathcal{P}$. Denoting by $\mathbf{x}\cdot \mathbf{y}$ the dot product of vectors $\mathbf{x}$ and $\mathbf{y}$, we have $$h=\mathbf{u}\cdot \overrightarrow{A_i{A}_k}=\mathbf{u}\cdot \left(\overrightarrow{A_i{A}_{i+1}}+\cdots +\overrightarrow{A_{k-1}{A}_k}\right)=\mathbf{u}\cdot \left(\overrightarrow{A_i{A}_{i-1}}+\cdots +\overrightarrow{A_{k+1}{A}_k}\right).$$ In $\mathcal{Q}$, the distance $H_i$ between the opposite sides $B_j{B}_{j+1}$ and $B_{j+n}{B}_{j+n+1}$ is given by $$H_i=\mathbf{u}\cdot \left(\overrightarrow{B_j{B}_{j+1}}+\cdots +\overrightarrow{B_{j+n-1}{B}_{j+n}}\right)=\mathbf{u}\cdot \left(\overrightarrow{{\mathbf{b}}_j}+\overrightarrow{{\mathbf{b}}_{j+1}}+\cdots +\overrightarrow{{\mathbf{b}}_{j+n-1}}\right).$$ The choice of vertex $A_k$ implies that the $n$ consecutive vectors $\overrightarrow{{\mathbf{b}}_j},\overrightarrow{{\mathbf{b}}_{j+1}},\dots ,\overrightarrow{{\mathbf{b}}_{j+n-1}}$ are precisely $\overrightarrow{A_i{A}_{i+1}},\dots ,\overrightarrow{A_{k-1}{A}_k}$ and $\overrightarrow{A_i{A}_{i-1}},\dots ,\overrightarrow{A_{k+1}{A}_k}$, taken in some order. This implies $H_i=2h_i$.

For a proof of (1), apply the lemma to each side of $\mathcal{P}$. If $O$ is the centre of $\mathcal{Q}$ then, using the notation of the lemma, $$[B_j{B}_{j+1}O]=[B_{j+n}{B}_{j+n+1}O]=[A_i{A}_{i+1}{A}_k]=S_i$$ Summation over all sides of $\mathcal{P}$ yields (1).

Set $d(\mathcal{P})=[\mathcal{Q}]-4[\mathcal{P}]$ for a convex polygon $\mathcal{P}$ with associate $\mathcal{Q}$. Inequality (2) means that $d(\mathcal{P})\ge 0$ for each convex polygon $\mathcal{P}$. The last inequality will be proved by induction on the number $\ell$ of side directions of $\mathcal{P}$, i.e. the number of pairwise nonparallel lines each containing a side of $\mathcal{P}$.

We choose to start the induction with $\ell =1$ as a base case, meaning that certain degenerate polygons are allowed. More exactly, we regard as degenerate convex polygons all closed polygonal lines of the form $X_1{X}_2\dots X_k{Y}_1{Y}_2\dots Y_m{X}_1$, where $X_1,X_2,\dots ,X_k$ are points in this order on a line segment $X_1{Y}_1$, and so are $Y_m,Y_{m-1},\dots ,Y_1$. The initial construction applies to degenerate polygons; their associates are also degenerate, and the value of $d$ is zero.

For the inductive step, consider a convex polygon $\mathcal{P}$ which determines $\ell$ side directions, assuming that $d(\mathcal{P})\ge 0$ for polygons with smaller values of $\ell$.

Suppose first that $\mathcal{P}$ has a pair of parallel sides, i.e. sides on distinct parallel lines. Let $A_i{A}_{i+1}$ and $A_j{A}_{j+1}$ be such a pair, and let $A_i{A}_{i+1}\le A_j{A}_{j+1}$. Remove from $\mathcal{P}$ the parallelogram $R$ determined by vectors $\overrightarrow{A_i{A}_{i+1}}$ and $\overrightarrow{A_i{A}_{j+1}}$. Two polygons are obtained in this way. Translating one of them by vector $\overrightarrow{A_i{A}_{i+1}}$ yields a new convex polygon ${\mathcal{P}}^{\prime }$, of area $[\mathcal{P}]-[R]$ and with value of $\ell$ not exceeding the one of $\mathcal{P}$. The construction just described will be called operation A.



The associate of ${\mathcal{P}}^{\prime }$ is obtained from $\mathcal{Q}$ upon decreasing the lengths of two opposite sides by an amount of $2A_i{A}_{i+1}$. By the lemma, the distance between these opposite sides is twice the distance between $A_i{A}_{i+1}$ and $A_j{A}_{j+1}$. Thus operation $\mathbf{A}$ decreases $[\mathcal{Q}]$ by the area of a parallelogram with base and respective altitude twice the ones of $R$, i.e. by $4[R]$. Hence $\mathbf{A}$ leaves the difference $d(\mathcal{P})=[\mathcal{Q}]-4[\mathcal{P}]$ unchanged.

Now, if ${\mathcal{P}}^{\prime }$ also has a pair of parallel sides, apply operation $\mathbf{A}$ to it. Keep doing so with the subsequent polygons obtained for as long as possible. Now, A decreases the number $p$ of pairs of parallel sides in $\mathcal{P}$. Hence its repeated applications gradually reduce $p$ to $0$, and further applications of $\mathbf{A}$ will be impossible after several steps. For clarity, let us denote by $\mathcal{P}$ again the polygon obtained at that stage.

The inductive step is complete if $\mathcal{P}$ is degenerate. Otherwise $\ell >1$ and $p=0$, i.e. there are no parallel sides in $\mathcal{P}$. Observe that then $\ell \ge 3$. Indeed, $\ell =2$ means that the vertices of $\mathcal{P}$ all lie on the boundary of a parallelogram, implying $p>0$.

Furthermore, since $\mathcal{P}$ has no parallel sides, consecutive collinear vectors in the sequence $\left(\overrightarrow{{\mathbf{b}}_k}\right)$ (if any) correspond to consecutive $180^{\circ }$-angles in $\mathcal{P}$. Removing the vertices of such angles, we obtain a convex polygon with the same value of $d(\mathcal{P})$.

In summary, if operation $\mathbf{A}$ is impossible for a nondegenerate polygon $\mathcal{P}$, then $\ell \ge 3$. In addition, one may assume that $\mathcal{P}$ has no angles of size $180^{\circ }$.

The last two conditions then also hold for the associate $\mathcal{Q}$ of $\mathcal{P}$, and we perform the following construction. Since $\ell \ge 3$, there is a side $B_j{B}_{j+1}$ of $\mathcal{Q}$ such that the sum of the angles at $B_j$ and $B_{j+1}$ is greater than $180^{\circ }$. (Such a side exists in each convex $k$-gon for $k>4$.) Naturally, $B_{j+n}{B}_{j+n+1}$ is a side with the same property. Extend the pairs of sides $B_{j-1}{B}_j,B_{j+1}{B}_{j+2}$ and $B_{j+n-1}{B}_{j+n},B_{j+n+1}{B}_{j+n+2}$ to meet at $U$ and $V$, respectively. Let ${\mathcal{Q}}^{\prime }$ be the centrally symmetric convex $2(n+1)$-gon obtained from $\mathcal{Q}$ by inserting $U$ and $V$ into the sequence $B_1,\dots ,B_{2n}$ as new vertices between $B_j,B_{j+1}$ and $B_{j+n},B_{j+n+1}$, respectively. Informally, we adjoin to $\mathcal{Q}$ the congruent triangles $B_j{B}_{j+1}U$ and $B_{j+n}{B}_{j+n+1}V$. Note that $B_j,B_{j+1},B_{j+n}$ and $B_{j+n+1}$ are kept as vertices of ${\mathcal{Q}}^{\prime }$, although $B_j{B}_{j+1}$ and $B_{j+n}{B}_{j+n+1}$ are no longer its sides.

Let $A_i{A}_{i+1}$ be the side of $\mathcal{P}$ such that $\overrightarrow{A_i{A}_{i+1}}=\overrightarrow{B_j{B}_{j+1}}=\overrightarrow{{\mathbf{b}}_j}$. Consider the point $W$ such that triangle $A_i{A}_{i+1}W$ is congruent to triangle $B_j{B}_{j+1}U$ and exterior to $\mathcal{P}$. Insert $W$ into the sequence $A_1,A_2,\dots ,A_n$ as a new vertex between $A_i$ and $A_{i+1}$ to obtain an $(n+1)$-gon ${\mathcal{P}}^{\prime }$. We claim that ${\mathcal{P}}^{\prime }$ is convex and its associate is ${\mathcal{Q}}^{\prime }$.



Vectors $\overrightarrow{A_{i}W}$ and $\overrightarrow{{\mathbf{b}}_{j-1}}$ are collinear and have the same direction, as well as vectors $\overrightarrow{W{A}_{i+1}}$ and $\overrightarrow{{\mathbf{b}}_{j+1}}$. Since $\overrightarrow{{\mathbf{b}}_{j-1}},\overrightarrow{{\mathbf{b}}_j},\overrightarrow{{\mathbf{b}}_{j+1}}$ are consecutive terms in the sequence $\left(\overrightarrow{{\mathbf{b}}_k}\right)$, the angle inequalities $\angle (\overrightarrow{{\mathbf{b}}_{j-1}},\overrightarrow{{\mathbf{b}}_j})\le \angle (\overrightarrow{A_{i-1}{A}_i},\overrightarrow{{\mathbf{b}}_j})$ and $\angle (\overrightarrow{{\mathbf{b}}_j},\overrightarrow{{\mathbf{b}}_{j+1}})\le \angle (\overrightarrow{{\mathbf{b}}_j},\overrightarrow{A_{i+1}{A}_{i+2}})$ hold true. They show that ${\mathcal{P}}^{\prime }$ is a convex polygon. To construct its associate, vectors $\pm \overrightarrow{A_i{A}_{i+1}}=\pm \overrightarrow{{\mathbf{b}}_j}$ must be deleted from the defining sequence $\left(\overrightarrow{{\mathbf{b}}_k}\right)$ of $\mathcal{Q}$, and the vectors $\pm \overrightarrow{A_{i}W},\pm \overrightarrow{W{A}_{i+1}}$ must be inserted appropriately into it. The latter can be done as follows: $$\dots ,\overrightarrow{{\mathbf{b}}_{j-1}},\overrightarrow{A_{i}W},\overrightarrow{W{A}_{i+1}},\overrightarrow{{\mathbf{b}}_{j+1}},\dots ,-\overrightarrow{{\mathbf{b}}_{j-1}},-\overrightarrow{A_{i}W},-\overrightarrow{W{A}_{i+1}},-\overrightarrow{{\mathbf{b}}_{j+1}},\dots .$$ This updated sequence produces ${\mathcal{Q}}^{\prime }$ as the associate of ${\mathcal{P}}^{\prime }$.

It follows from the construction that $[{\mathcal{P}}^{\prime }]=[\mathcal{P}]+[A_i{A}_{i+1}W]$ and $[{\mathcal{Q}}^{\prime }]=[\mathcal{Q}]+2[A_i{A}_{i+1}W]$. Therefore $d({\mathcal{P}}^{\prime })=d(\mathcal{P})-2[A_i{A}_{i+1}W]<d(\mathcal{P})$.

To finish the induction, it remains to notice that the value of $\ell$ for ${\mathcal{P}}^{\prime }$ is less than the one for $\mathcal{P}$. This is because side $A_i{A}_{i+1}$ was removed. The newly added sides $A_{i}W$ and $W{A}_{i+1}$ do not introduce new side directions. Each one of them is either parallel to a side of $\mathcal{P}$ or lies on the line determined by such a side. The proof is complete.