\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Shortlist 2006 C6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 15}
\maketitle
\section*{Problem}
An upward equilateral triangle of side length $n$
is divided into $n^2$ cells which are equilateral triangles of unit length.
A \emph{holey triangle} is such a triangle
with $n$ upward unit triangular holes cut out along gridlines.
A diamond is a $60^\circ-120^\circ$ unit rhombus.
Prove that a holey triangle $T$ can be tiled with diamonds
if and only if the following condition holds:
Every upward equilateral triangle of side length $k$ in $T$
contains at most $k$ holes, for $1 \le k \le n$.
\section*{Video}
\href{https://www.youtube.com/watch?v=n7Z5I5I0R-c&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/n7Z5I5I0R-c}}
\section*{External Link}
\url{https://aops.com/community/p875004}
\newpage
\section*{Solution}
The idea is to show that the condition in the problem
is equivalent to the condition in Hall's Marriage Lemma,
wherein we try to match down-triangles to non-hole up-triangles.
To this end, let's say two holes are \emph{adjacent}
if they share a vertex,
and a set of holes is \emph{connected} if they form
a connected component with respect to the adjacency condition.
Finally, the \emph{bounding box} of a set of holes
is the smallest upwards equilateral triangle of some side length
(by inclusion) that contains all the triangles.
\begin{claim*}
Consider a connected set $D$ of down-triangles
which has a bounding box of side length $k$.
Then at least $\left\lvert D \right\rvert + k$ up-triangles are adjacent
to at least one of the down-triangles in $D$.
\end{claim*}
\begin{proof}
[Outline of proof]
The idea is to go by induction on $|D|$,
by deleting the uppermost triangle which touches
the left boundary of the bounding box of $D$.
(The catch is that doing this deletion may disconnect $D$,
so this case needs to be handled as well.)
\end{proof}
Suppose the problem condition holds; we prove Hall's condition.
Consider a general set $\mathcal D$ of down-triangles.
The $\mathcal D$ is the disjoint union $D_1 \sqcup \dots \sqcup D_k$
of $k$ connected components.
The problem condition implies that now that
there are at least $|D_i|$ up-holes neighboring some down-hole in $D_i$,
and any up-hole is adjacent to down-triangles in at most one $D_i$;
so Hall's condition holds for $\mathcal D$.
For the converse direction,
if Hall's condition holds,
taking $\mathcal D$ to be all the down-triangles in some
equilateral triangle of side length $k$ implies the result.
(This does not need the claim; it is the easy direction.)
\end{document}