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

\begin{document}
\title{USAMO 1999/1}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 41}
\maketitle

\section*{Problem}
Some checkers placed on an $n \times n$ checkerboard satisfy the following conditions:
\begin{enumerate}
  \ii[(a)] every square that does not contain a checker shares a side with one that does;
  \ii[(b)] given any pair of squares that contain checkers,
  there is a sequence of squares containing checkers,
  starting and ending with the given squares,
  such that every two consecutive squares of the sequence share a side.
\end{enumerate}
Prove that at least $(n^{2}-2)/3$ checkers have been placed on the board.

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

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

\newpage

\section*{Solution}
Take a spanning tree on the set $V$ of checkers
where the $|V|-1$ edges of the tree are given by orthogonal adjacency.
By condition (a) we have
\[ \sum_{v \in V} (4-\deg v) \ge n^2 - |V| \]
and since $\sum_{v \in V} \deg v = 2(|V|-1)$ we get
\[ 4|V| - \left( 2|V|-2 \right) \ge n^2 - |V| \]
which implies $|V| \ge \frac{n^2-2}{3}$.

\end{document}
