, 2006

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 $AA', BB'$. 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 $AA'$ 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 $AA'$. Consider the sequence of main diagonals $AA', BB', CC', \ldots$, where $A, B, C, \ldots$ are consecutive vertices, situated right to $AA'$. The $n$-th item in this sequence is the diagonal $A'A$ (i.e. $AA'$ reversed), having $X$ on its right side. So there are two successive vertices $K, L$ in the sequence $A, B, C, \ldots$ before $A'$ such that $X$ still lies to the left of $KK'$ but to the right of $LL'$. And this means that $X$ is in the triangle $\Delta_{\ell'}$, $\ell' = K' L'$. Analogous reasoning applies to points $X$ on the right of $AA'$ (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' = A'B'$ (with $AA', BB'$ main diagonals) such that $[\Delta_{b}] + [\Delta_{b'}] \geq S / n$, where $[\cdots]$ stands for the area of a region. Let $AA', BB'$ intersect at $P$; assume without loss of generality that $PB \geq PB'$. Then
$$[ABA'] = [ABP] + [PBA'] \geq [ABP] + [PA'B'] = [\Delta_{b}] + [\Delta_{b'}] \geq S / n,$$
proving the lemma. $\square$

Now, let $\mathcal{P}$ be any convex polygon, of area $S$, with $m$ sides $a_{1}, \ldots, 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}, \ldots, 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}, \ldots, 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] \geq 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] \geq k_{i} \cdot S / n = q_{i} \cdot S > S_{i},$$
in contradiction with the definition of $S_{i}$. This ends the proof.

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} \ldots A_{n}$ we assign a centrally symmetric convex $(2n)$-gon $\mathcal{Q}$ with side vectors $\pm \overrightarrow{A_{i} A_{i+1}}, 1 \leq i \leq 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}}, \ldots, \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}}, \ldots, \overrightarrow{\mathbf{b}_{j+r}}$. One can assume that in such cases the respective opposite vectors occur in the order $-\overrightarrow{\mathbf{b}_{j}}', -\overrightarrow{\mathbf{b}_{j+1}}, \ldots, -\overrightarrow{\mathbf{b}_{j+r}}$, ensuring that $\overrightarrow{\mathbf{b}_{j+n}} = -\overrightarrow{\mathbf{b}_{j}}$ for $j = 1, \ldots, 2n$. Indices are taken cyclically here and in similar situations below.

Choose points $B_{1}, B_{2}, \ldots, B_{2n}$ satisfying $\overrightarrow{B_{j} B_{j+1}} = \overrightarrow{\mathbf{b}_{j}}$ for $j = 1, \ldots, 2n$. The polygonal line $\mathcal{Q} = B_{1} B_{2} \ldots 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 \leq i \leq 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, \ldots, n$. Note that $B_{j} B_{j+1}$ and $B_{j+n} B_{j+n+1}$ are opposite sides of $\mathcal{Q}$, $1 \leq j \leq 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 \leq i \leq n$. We prove that
$$\left[ B_{1} B_{2} \ldots B_{2n} \right] = 2 \sum_{i=1}^{n} S_{i} \tag{1}$$
and
$$\left[ B_{1} B_{2} \ldots B_{2n} \right] \geq 4 \left[ A_{1} A_{2} \ldots A_{n} \right] \tag{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, \ldots, 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 $2 h_{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}}, \ldots, \overrightarrow{\mathbf{b}_{j+n-1}}$ are precisely $\overrightarrow{A_{i} A_{i+1}}, \ldots, \overrightarrow{A_{k-1} A_{k}}$ and $\overrightarrow{A_{i} A_{i-1}}, \ldots, \overrightarrow{A_{k+1} A_{k}}$, taken in some order. This implies $H_{i} = 2 h_{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}) \geq 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} \ldots X_{k} Y_{1} Y_{2} \ldots Y_{m} X_{1}$, where $X_{1}, X_{2}, \ldots, X_{k}$ are points in this order on a line segment $X_{1} Y_{1}$, and so are $Y_{m}, Y_{m-1}, \ldots, 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}) \geq 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} \leq 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}'$, 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}'$ is obtained from $\mathcal{Q}$ upon decreasing the lengths of two opposite sides by an amount of $2 A_{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}'$ 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 \geq 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 \geq 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 \geq 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}'$ be the centrally symmetric convex $2(n+1)$-gon obtained from $\mathcal{Q}$ by inserting $U$ and $V$ into the sequence $B_{1}, \ldots, 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}'$, 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}, \ldots, A_{n}$ as a new vertex between $A_{i}$ and $A_{i+1}$ to obtain an $(n+1)$-gon $\mathcal{P}'$. We claim that $\mathcal{P}'$ is convex and its associate is $\mathcal{Q}'$.

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}} ) \leq \angle( \overrightarrow{A_{i-1} A_{i}}, \overrightarrow{\mathbf{b}_{j}} )$ and $\angle( \overrightarrow{\mathbf{b}_{j}}, \overrightarrow{\mathbf{b}_{j+1}} ) \leq \angle( \overrightarrow{\mathbf{b}_{j}}, \overrightarrow{A_{i+1} A_{i+2}} )$ hold true. They show that $\mathcal{P}'$ 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:
$$\ldots, \overrightarrow{\mathbf{b}_{j-1}}, \overrightarrow{A_{i} W}, \overrightarrow{W A_{i+1}}, \overrightarrow{\mathbf{b}_{j+1}}, \ldots, -\overrightarrow{\mathbf{b}_{j-1}}, -\overrightarrow{A_{i} W}, -\overrightarrow{W A_{i+1}}, -\overrightarrow{\mathbf{b}_{j+1}}, \ldots.$$
This updated sequence produces $\mathcal{Q}'$ as the associate of $\mathcal{P}'$.

It follows from the construction that $[\mathcal{P}'] = [\mathcal{P}] + [A_{i} A_{i+1} W]$ and $[\mathcal{Q}'] = [\mathcal{Q}] + 2 [A_{i} A_{i+1} W]$. Therefore $d(\mathcal{P}') = 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}'$ 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.