\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Cono Sur 2011/6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 32}
\maketitle
\section*{Problem}
Let $Q$ be a $(2n+1) \times (2n+1)$ board.
Some of its cells are colored black in such a way that every $2 \times 2$
board of $Q$ has at most $2$ black cells.
Find the maximum amount of black cells that the board may have.
\section*{Video}
\href{https://www.youtube.com/watch?v=S6AYLVuUzn8&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/S6AYLVuUzn8}}
\newpage
\section*{Solution}
The answer is $(n+1)(2n+1)$ achieved by coloring all the odd numbered rows.
We proceed by induction on $n$ with the base case $n=0$ being clear.
For the other direction, we are going to decompose our $(2n+1)\times(2n+1)$
board into a $2 \times 2$ square, two $2 \times (2n-1)$ strips,
and a $(2n-1) \times (2n-1)$ square, as shown below.
\begin{center}
\begin{asy}
size(6cm);
filldraw(box( (0,0), (2,7) ), palegreen, blue+1);
filldraw(box( (2,7), (9,9) ), palegreen, blue+1);
filldraw(box( (0,7), (2,9) ), palered, blue+1);
for (int i=0; i<=9; ++i) {
draw( (0,i)--(9,i), grey );
draw( (i,0)--(i,9), grey );
}
filldraw(box((2,0), (9,7)), paleyellow, blue+1);
label("$(2n-1) \times (2n-1)$", (5.5, 3.5), blue);
\end{asy}
\end{center}
To get the bound, we observe that:
\begin{itemize}
\ii The red $2 \times 2$ square has at most two black cells.
\ii The western green rectangle has at most $2n$ black cells,
with equality if and only if the rows of length $2$
are shaded alternating black.
The same is true for the northern green rectangle.
\ii However, equality cannot simultaneously occur:
if the two green rectangles both have $2n$ black cells,
then the red $2 \times 2$ square has at most one black cell (at the
northwestern corner).
\end{itemize}
Hence, outside the yellow square, there are at most
$(2n + 2n + 2) - 1 = 4n+1$ black squares.
Now, induction gives a bound of
\[ \underbrace{n \cdot (2n-1)}_{\text{by IH}} +
\underbrace{(4n+1)}_{\text{green/red}} = (n+1)(2n+1). \]
\end{document}