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

\begin{document}
\title{Ireland 1994/10}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 87}
\maketitle

\section*{Problem}
Fix an integer $n \ge 1$.
A square is partitioned into $n$ convex polygons,
A line segment which joins two vertices of polygons in the dissection,
and does not contain any other vertices of the polygons in its interior,
is called a \emph{basic} segment.

Determine the maximum number of basic segments
which could be present in such a dissection, in terms of $n$.

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

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

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