\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{USEMO 2021/1}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 89}
\maketitle
\section*{Problem}
Let $n$ be a positive integer and
consider an $n \times n$ grid of real numbers.
Determine the greatest possible number of cells $c$ in the grid such that
the entry in $c$ is both strictly \emph{greater} than the average of $c$'s column
and strictly \emph{less} than the average of $c$'s row.
\section*{Video}
\href{https://youtu.be/kjcY8qQAi5U}{\texttt{https://youtu.be/V-9UBJr7aDI}}
\newpage
\section*{Solution}
The answer is $(n-1)^2$.
An example is given by the following construction,
shown for $n=5$, which generalizes readily.
Here, the lower-left $(n-1) \times (n-1)$ square gives a bound.
\[
\begin{bmatrix}
-1 & -1 & -1 & -1 & 0 \\
0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 1
\end{bmatrix}
\]
We give two proofs of the bound.
Call a cell \emph{good} if it satisfies the condition of the problem.
\paragraph{Coloring proof, from the author}
We now prove that no more than $(n-1)^2$ squares can be good.
The cells are weakly ordered by $\ge$ (there may be some ties due to equal elements);
we arbitrarily extend it to a total ordering $\gtrdot$, breaking all ties.
(Alternatively, one can phrase this as perturbing the grid entries
in such a way that they become distinct.)
\begin{itemize}
\ii For every column, we color red the $\gtrdot$-smallest element in that column.
\ii For every row, we color blue the $\gtrdot$-largest element in that row.
\end{itemize}
This means that there are exactly $n$ red and $n$ blue cells.
Note that these cells are never good.
\begin{claim*}
There is at most one cell that is both red and blue.
\end{claim*}
\begin{proof}
Assume for contradiction that $P_1$ and $P_2$ are two ``purple'' cells (both red and blue).
Look at the resulting picture
\[ \begin{bmatrix}
P_1 & x \\
y & P_2
\end{bmatrix}.
\]
By construction, we have $P_1 \gtrdot x \gtrdot P_2 \gtrdot y \gtrdot P_1$.
This is a contradiction.
\end{proof}
Thus at least $2n-1$ cells cannot be good. This proves the bound.
\paragraph{Proof using K\"{o}nig's theorem, from Ankan Bhattacharya}
This proof is based on the following additional claim:
\begin{claim*}
No column/row can be all-good,
and no transversal can be all-good.
\end{claim*}
\begin{proof}
The first part is obvious. As for the second,
let $r_i$ and $c_j$ denote the column sums.
If cell $(i, j)$ is good, then
\[ r_i < a_{i, j} < c_j. \]
If we have a good transversal,
summing the inequality $r_i < c_j$
over the cells in this transversal gives a contradiction
(as $\sum r_\bullet = \sum c_\bullet$).
\end{proof}
This claim alone is enough to imply the desired bound.
\begin{claim*}
There exists a choice of $a$ columns and $b$ rows,
with $a+b=n+1$, such that no good cells
lie on the intersection of the columns and rows.
\end{claim*}
\begin{proof}
Follows by \emph{K\"onig's theorem}, and the previous claim.
Alternatively, quote the contrapositive of Hall's marriage theorem:
because there was no all-good transversal,
there must be a set of $a$ columns with
more than $n-a$ ``compatible'' rows.
\end{proof}
Suppose $a \le \frac n2 \le b$; the other case is similar.
Now we bound:
\begin{itemize}
\ii The $a \times b$ cells of the claim are given to be all non-good.
\ii In the $n - a = b - 1$ remaining rows,
there is at least one more non-good cell.
\end{itemize}
Thus the number of non-good cells is at least
\[ ab + (b - 1) = (a+1)b - 1 \ge 2 \cdot n - 1 = n^2 - (n-1)^2, \]
and so there are at most $(n-1)^2$ good cells.
\end{document}