\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/kjcY8qQAi5U}}

\section*{External Link}
\url{https://aops.com/community/p23517195}

\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}
