Problem: 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$.

\end{enumerate}

Solution: We say a polygon in \emph{almost convex}
if all its angles are at most $180\dg$.

Note that given any convex or almost convex polygon,
we can take any side $b$ and add another vertex on it, and the sum of the labels doesn't change
(since the label of a side is the length of the side times the distance of the farthest point).

\begin{lemma*}
  Let $N$ be an even integer.
  Then any almost convex $N$-gon with area $S$
  should have an inscribed triangle with area at least $2S/N$.
\end{lemma*}
The main work is the proof of the lemma.

Label the polygon $P_0 P_1 \dots P_{N-1}$.
Consider the $N/2$ major diagonals of the almost convex $N$-gon,
$P_0 P_{N/2}$, $P_1 P_{N/2+1}$, et cetera.
A \emph{butterfly} refers to a self-intersecting quadrilateral
$P_i P_{i+1} P_{i+1+N/2} P_{i+N/2}$.
An example of a butterfly is shown below for $N=8$.
\begin{center}
\begin{asy}
pair P_0 = (-1,-3);
pair P_1 = ( 0,-3);
pair P_2 = (2.5,-3);
pair P_3 = (3,0);
pair P_4 = (1.8,1.2);
pair P_5 = (1.1,1.9);
pair P_6 = (0.3,2.7);
pair P_7 = (-2,0.4);
filldraw(P_0--P_2--P_3--P_6--P_7--cycle, opacity(0.1)+lightcyan, blue);

filldraw(P_0--P_4--P_5--P_1--cycle, opacity(0.2)+lightred, red);
draw(P_1--P_5, red);
draw(P_2--P_6, red);
draw(P_3--P_7, red);

dot("$P_0$", P_0, dir(P_0));
dot("$P_1$", P_1, dir(P_1));
dot("$P_2$", P_2, dir(P_2));
dot("$P_3$", P_3, dir(P_3));
dot("$P_4$", P_4, dir(P_4));
dot("$P_5$", P_5, dir(P_5));
dot("$P_6$", P_6, dir(P_6));
dot("$P_7$", P_7, dir(P_7));

/* TSQ Source:

P_0 = (-1,-3)
P_1 = ( 0,-3)
P_2 = (2.5,-3)
P_3 = (3,0)
P_4 = (1.8,1.2)
P_5 = (1.1,1.9)
P_6 = (0.3,2.7)
P_7 = (-2,0.4)
P_0--P_2--P_3--P_6--P_7--cycle 0.1 lightcyan / blue

P_0--P_4--P_5--P_1--cycle 0.2 lightred / red
P_1--P_5 red
P_2--P_6 red
P_3--P_7 red

*/
\end{asy}
\end{center}

\begin{claim*}
  Every point $X$ in the polygon is contained in the wingspan of some butterfly.
\end{claim*}
\begin{proof}
  Consider a windmill-like process which
  \begin{itemize}
    \ii starts from some oriented red line $P_0 P_{N/2}$, oriented to face $P_0 P_{N/2}$
    \ii rotates through $P_0 P_{N/2} \cap P_1 P_{N/2+1}$ to get line $P_1 P_{N/2+1}$,
    \ii rotates through $P_1 P_{N/2+1} \cap P_2 P_{N/2+2}$ to get line $P_2 P_{N/2+2}$,
    \ii \dots et cetera, until returning to line $P_{N/2} P_0$,
    but in the reverse orientation.
  \end{itemize}
  At the end of the process, every point in the plane has switched sides with our moving line.
  The moment that $X$ crosses the moving red line, we get it contained in a butterfly, as needed.
\end{proof}

\begin{claim*}
  If $ABDC = P_i P_{i+1} P_{i+1+N/2} P_{i+N/2}$ is a butterfly,
  one of the triangles $ABC$, $BCD$, $CDA$, $DAB$
  has area at least that of the butterfly.
\end{claim*}
\begin{proof}
  Let the diagonals of the butterfly meet at $O$,
  and let $a = AO$, $b = BO$, $c = CO$, $d = DO$.
  If we assume WLOG $d = \min(a,b,c,d)$
  then it follows $[ABC] = [AOB] + [BOC] \ge [AOB] + [COD]$, as needed.
\end{proof}

Now, since the $N/2$ butterflies cover an area of $S$,
it follows that one of the butterflies
has area at least $S / (N/2) = 2S/N$,
and so that butterfly gives a triangle with area at least $2S/N$,
completing the proof of the lemma.

\paragraph{Main proof.}
Let $a_1$, \dots, $a_n$ be the numbers assigned to the sides.
Assume for contradiction $a_1 + \dots + a_n < 2S$.
We pick even integers $m_1$, $m_2$, \dots, $m_n$ such that
\begin{align*}
  \frac{a_1}{S} &< \frac{2m_1}{m_1 + \dots + m_n} \\
  \frac{a_2}{S} &< \frac{2m_2}{m_1 + \dots + m_n} \\
  &\vdotswithin\le \\
  \frac{a_n}{S} &< \frac{2m_n}{m_1 + \dots + m_n}.
\end{align*}
which is possible by rational approximation,
since the right-hand sides sum to $2$ and the left-hand sides sum to strictly less than $2$.

Now we break every side of $P$ into $m_i$ equal parts
to get an almost convex $N$-gon, where $N = m_1 + \dots + m_n$.

The main lemma then gives us a triangle $\Delta$ of the almost convex $N$-gon
which has area at least $\frac{2S}{N}$.
If $\Delta$ used the $i$th side then it then follows the label $a_i$ on that side should be
at least $m_i \cdot \frac{2S}{N}$, contradiction.