\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Ireland 1994/10}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 87}
\maketitle
\section*{Problem}
If a square is partitioned into $n$ convex polygons,
determine the maximum number of edges present in the resulting figure.
\section*{Video}
\href{https://www.youtube.com/watch?v=lt32pF046lU&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ&index=5}{\texttt{https://youtu.be/lt32pF046lU}}
\newpage
\section*{Solution}
The answer is $E \le 3n+1$.
One construction is to use parallel stripes.
(In fact, we will shortly see any construction
which does not use the corners of the square
and does not have four edges meeting at a point will
achieve this optimal $3n+1$.)
For the converse, we use the fact that
\[ V-E+F=2 \]
in the usual way, with $F=n+1$ because of the unbounded face.
The observation needed is only:
\begin{claim*}
Every vertex other than possibly the corners
of the original square have degree at least $3$.
\end{claim*}
\begin{proof}
Follows by convexity for vertices inside the square,
and immediate for vertices on the perimeter.
\end{proof}
The claim then implies
\[ 2E = \sum_{v \in V} \deg v \ge 2 \cdot 4 + 3(V-4) = 3V-4. \]
Combining this with Euler's formula $V-E+F=2$ gives
\begin{align*}
n-1 &= E-V \ge E - \frac{2E+4}{3} = \frac{E-4}{3}
\end{align*}
which gives the result.
\end{document}