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

\begin{document}
\title{Brazil 2022/6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 107}
\maketitle

\section*{Problem}
Some cells of a $10 \times 10$ grid 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=oxrY6brGYfg&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/oxrY6brGYfg}}

\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) {
  if ((x%11 != 0) && (y%11 != 0)) {
    filldraw(shift( (x%11),-(y%11) )*unitsquare, lightcyan, blue);
  } else {
    filldraw(shift( (x%11),-(y%11) )*unitsquare, rgb(1,0.9,0.9), dotted+red);
  }
}
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 most $47$ blue cells in a valid $10 \times 10$ grid.
  Also, if such a valid grid did exist,
  then there exists seven columns with at least $35$ blue cells among them.
\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.
  The unique choices of $a_i$ (up to permutation)
  for which $\sum a_i = 47$ and $\sum \binom{a_i}{2} < 90$
  are $3\binom42 + 7\binom52 = 88$
  and $4\binom42 + 5\binom52 + \binom62 = 89$;
  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.
From $\sum b_i \ge 35$ we have
\[ \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. \]

\paragraph{Another proof of bound (Jiahe Liu).}
Assume for contradiction there is a valid grid of $47$ blue cells
(if there are more than $47$ cells, arbitrarily uncolor some cells).
Let $a \leq b \leq c$ be the counts of blue cells in the rows with the fewest blue cells
(ties broken arbitrarily).

\begin{claim*}
  We must have $a+b+c \leq 12$.
\end{claim*}
\begin{proof}
  If $c \leq 4$, the result is clear.
  When $c \ge 5$, the other seven rows need to have at least $c$ cells, so we have
  \[ 47 \geq a+b+8c \implies a+b+c \leq 47-7c \leq 12. \qedhere \]
\end{proof}

Thus the remaining seven rows have at least $35$ blue cells among them.
We can now finish as in the first solution.

\end{document}
