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

\begin{document}
\title{ToT Fall 2005 S-A3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 74}
\maketitle

\section*{Problem}
Originally, every square of $8 \times 8$ chessboard contains a rook.
One by one, rooks which attack an odd number of other rooks are removed.
(Rooks may not jump over other rooks.)
Find the maximal number of rooks that can be removed.
(A rook attacks another rook if they are on the same row or column
and there are no other rooks between them.)

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

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

\newpage

\section*{Solution}
The answer is $59$.

\begin{claim*}
  At least $5$ rooks always remain.
\end{claim*}
\begin{proof}
  [Proof $\ge 5$ rooks always remain]
  To show that $5$ rooks must remain,
  observe first that the four corners may never be deleted
  (as long as all four corners are present,
  these rooks attack exactly $2$ others).
  Moreover, if there are $5$ rooks left on the board,
  the non-corner rook cannot be removed by inspection.
\end{proof}

Here is the construction.
Each cell is labeled with the time it is removed.
They are color coded for convenience.
\[
\begin{bmatrix}
{\bigstar} & {\color{red}1} & {\color{red}2} & {\color{red}3} &
  {\color{red}4} & {\color{red}5} & {\color{red}6} & {\bigstar} \\
  {\color{blue}13} & 50 & 51 & 52 & 53 & 54 & 55 & {\color{red}7} \\
  {\color{blue}14} & {\color{blue}15} & {\color{blue}16} &
  {\color{blue}17} & {\color{blue}18} & {\color{blue}19} & 56
  & {\color{red}8} \\
  {\color{blue}20} & {\color{blue}21} & {\color{blue}22} &
  {\color{blue}23} & {\color{blue}24} & {\color{blue}25} & 57
  & {\color{red}9} \\
  {\color{blue}26} & {\color{blue}27} & {\color{blue}28} &
  {\color{blue}29} & {\color{blue}30} & {\color{blue}31} & 58
  & {\color{red}10} \\
  {\color{blue}32} & {\color{blue}33} & {\color{blue}34} &
  {\color{blue}35} & {\color{blue}36} & {\color{blue}37} & 59
  & {\color{red}11} \\
  {\color{blue}38} & {\color{blue}39} & {\color{blue}40} &
  {\color{blue}41} & {\color{blue}42} & {\color{blue}43} &
  {\bigstar} & {\color{red}12} \\
  {\bigstar} & {\color{green!70!black}44} & {\color{green!70!black}45}
  & {\color{green!70!black}46} & {\color{green!70!black}47}
  & {\color{green!70!black}48} & {\color{green!70!black}49}
  & {\bigstar}
\end{bmatrix}
\]

\end{document}
