\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Brazil 2022/6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 108}
\maketitle
\section*{Problem}
Some cells of a $10 \times 10$ are colored blue. A set of
six cells is called \emph{gremista}
when the cells are the intersection of three
rows and two columns, or two rows and three columns, and are painted blue.
Determine the greatest value of $n$ for which it is possible to color $n$
chessboard cells blue such that there is not a gremista set.
\section*{Video}
\href{https://www.youtube.com/watch?v=C9WhZldyMuc&t=4963s}{\texttt{https://youtu.be/C9WhZldyMuc}}
\section*{External Link}
\url{https://aops.com/community/p26563956}
\newpage
\section*{Solution}
The answer is $46$.
Call a grid \emph{valid} if no gremista cells exist.
\paragraph{Construction}
The construction is shown below in the thick green border,
which encloses a valid construction of a $10 \times 10$.
\begin{center}
\begin{asy}
void meow(int x, int y) {
filldraw(shift( (x%11),-(y%11) )*unitsquare, lightcyan, blue);
}
for (int y=0; y<11; ++y) {
meow(y, y);
meow(y+1, y);
meow(y+2, y);
meow(y+4, y);
meow(y+7, y);
}
draw(box( (1,0), (11,-10) ), deepgreen+2);
\end{asy}
\end{center}
The reason for the ``extra'' row and column is that
this construction is actually obtained by taking an $11 \times 11$ grid
and using cells $\{y, y+1, y+2, y+4, y+7\} \pmod{11}$
in the $y$'th row; this gives a valid $11 \times 11$ grid,
and deleting a single row and column of a valid $11 \times 11$
will always leave a valid $10 \times 10$.
\paragraph{Bound}
We start with:
\begin{claim*}
There must be at $47$ blue cells in an $10 \times 10$ valid grid.
Also, if such a valid grid did exist, it would have to have
exactly seven columns with exactly five blue cells each.
\end{claim*}
\begin{proof}
Let $a_i$ be the number of blue cells in the $i$th column.
Then the usual double-counting argument gives
\[ \sum_{1}^{10} \binom{a_i}{2} \le 2 \binom{10}{2} = 90. \]
Because $\binom{\bullet}{2}$ is convex,
for a fixed value of $\sum a_i$ the left-hand side
is minimized when any two $a_i$ differ by at most one.
So we find that the unique choice of $a_i$ (up to permutation)
for which $\sum a_i = 47$ and $\sum \binom{a_i}{2} < 90$
is $3\binom42 + 7\binom52 = 88$;
no such choices exist with $\sum a_i \ge 48$.
\end{proof}
But now we can repeat the same convexity argument on just those
seven columns; assuming for contradiction an example for $47$ did exist,
let $b_i$ denote the number of blue cells in the $i$th row
\emph{and} in those seven columns.
Then we have $\sum b_i = 7 \cdot 5 = 35$ yet
\[ \sum_{1}^{10} \binom{b_i}{2} \le 2 \binom 72 = 42 \]
but \[ \sum_{1}^{10} \binom{b_i}{2} > 10 \binom{3.5}{2} = 43.75 > 42. \]
\end{document}