\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{RMM 2008/4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 121}
\maketitle

\section*{Problem}
Consider a square of sidelength $n$ and $(n+1)^2$ interior points.
Prove that we can choose $3$ of these points so that
they determine a triangle (possibly degenerate) of area at most $\frac12$.

\section*{Video}
\href{https://www.youtube.com/watch?v=79W3dNyiYWw&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/79W3dNyiYWw}}

\section*{External Link}
\url{https://aops.com/community/p1030132}

\newpage

\section*{Solution}
Assume no $3$ points are collinear (else they are area $0$).
Suppose the convex hull of our polygon has $k \ge 3$ points.
We consider two cases.

\paragraph{First case: $k \le 4n$.}
If $k \le 4n$, we use the following algorithm: draw the entire convex hull,
and then repeatedly draw non-intersecting segments between pairs of points.
The end result is a division of the $k$-gon into triangles.

By double-counting interior angles, the number of triangles is given exactly by
\[
    \frac{360\dg \cdot \left( (n+1)^2-k \right) + 180\dg \cdot (k-2)}{180\dg}
    = 2n^2 + 4n - k \ge 2n^2.
\]
The sum of the areas of the triangles is at most $n^2$
(the total area of the square), so we're done.

\paragraph{Second case: $k \ge 4n$.}
We will show that we can take some three consecutive vertices of the convex hull.

Let $a_1$, \dots, $a_k$ be the side lengths of the convex hull in order.
A convex polygon contained inside a square of side length $n$
has perimeter at most $4n$, so we have $a_1 + \dots + a_k \le 4n$.
Using the lemma with $k \ge 4n$,
there should be an index $i$ with $a_i + a_{i+1} \le 2$.
It follows that $a_i a_{i+1} \le 1$ for some index $i$ by AM-GM.
The two associated sides then carve out a triangle of area at most $\half$.

\end{document}
