\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}