\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Centroamerican 2021/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 81}
\maketitle
\section*{Problem}
In a table consisting of $2021\times 2021$ unit squares,
some unit squares are colored black in such a way that if we place a mouse
in the center of any square on the table it can walk in a straight line
(up, down, left or right along a column or row) and
leave the table without walking on any black square (other than the initial one if it is black).
What is the maximum number of squares that can be colored black?
\section*{Video}
\href{https://www.youtube.com/watch?v=H0HNe0I1WQI&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ&index=18}{\texttt{https://youtu.be/H0HNe0I1WQI}}
\newpage
\section*{Solution}
The answer with $2021$ replaced by $n$ is $4n-4$.
A construction is shown below for $n=9$ that obviously generalizes,
with black squares marked by $\blacksquare$
\[
\begin{bmatrix}
\blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare
& \blacksquare & \blacksquare & \blacksquare & \blacksquare \\
\blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare
& \blacksquare & \blacksquare & \blacksquare & \blacksquare \\
\blacksquare &&&&&&&& \blacksquare \\
\blacksquare &&&&&&&& \blacksquare \\
\blacksquare &&&&&&&& \blacksquare \\
\blacksquare &&&&&&&& \blacksquare \\
\blacksquare &&&&&&&& \blacksquare \\
\blacksquare &&&&&&&& \blacksquare \\
\blacksquare &&&&&&&& \blacksquare \\
\blacksquare &&&&&&&& \blacksquare \\
\end{bmatrix}
\]
To show this bound is tight, we do the following:
from each black square, shine a laser towards the edge of the board
passing through only white squares according to the path the mouse would take.
For black squares that are on the damn edge of the board,
we specifically choose to shine the laser towards the adjacent wall
(i.e.\ of length $1$).
Then, each edge of chessboard is hit by at most one laser.
Moreover, at the corner of the board,
we observe that the walls for the first row and first column
can be hit at most once (they are only accessible from the laser at that corner).
So this implies a bound of $4(n-1)$, as needed.
\end{document}