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

\begin{document}
\title{JBMO SL 2018 C3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 71}
\maketitle

\section*{Problem}
The cells of a $8 \times 8$ table are initially white.
Alice and Bob play a game.
First Alice paints $n$ of the cells in red.
Then Bob chooses $4$ rows and $4$ columns
from the table and paints all cells in them in black.
Alice wins if there is at least one red cell left.
Find the least value of $n$ such that Alice
can win the game no matter how Bob plays.

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

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

\newpage

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

To show that $n \le 12$ is winning for Bob,
note that Bob can simply take the four most populated rows;
this removes at least $8$ red cells, and Bob can cover the rest.

On the other hand, Alice wins when $n = 13$ using the following set of red cells:
\[
  \begin{array}{|cccccccc|}
    \hline
    {\color{red}\blacksquare} & . & . & . & {\color{red}\blacksquare} & . & . & . \\
    {\color{red}\blacksquare} & {\color{red}\blacksquare} & . & . & . & . & . & . \\
    . & {\color{red}\blacksquare} & {\color{red}\blacksquare} & . & . & . & . & . \\
    . & . & {\color{red}\blacksquare} & {\color{red}\blacksquare} & . & . & . & . \\
    . & . & . & {\color{red}\blacksquare}  & {\color{red}\blacksquare} & . & . & . \\
    . & . & . & . & . & {\color{red}\blacksquare} & . & . \\
    . & . & . & . & . & . & {\color{red}\blacksquare} & . \\
    . & . & . & . & . & . & . & {\color{red}\blacksquare} \\ \hline
  \end{array}
\]

\begin{remark*}
  [Motivation]
  In general, one inductive idea is to find a red cell which is in only one row,
  and a red cell which is in only one column.
  These can be used to try and inductive approach, unless the cells happen to coincide.
  However, it is also fatal to have more than four such super-isolated cells for Alice.
  This leads to the construction above with exactly three such cells.
\end{remark*}

\end{document}
