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 greater than the average of $c$ 's column and strictly less than the average of c's row.
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.
$$
\left[\begin{array}{ccccc}
-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{array}\right]
$$

We give two proofs of the bound. Call a cell good if it satisfies the condition of the problem.

ब 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 $\geq$ (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.)
- For every column, we color red the $>$-smallest element in that column.
- For every row, we color blue the $>$-largest element in that row.

This means that there are exactly $n$ red and $n$ blue cells. Note that these cells are never good.
Claim - There is at most one cell that is both red and blue.

Proof. Assume for contradiction that $P_{1}$ and $P_{2}$ are two "purple" cells (both red and blue). Look at the resulting picture
$$
\left[\begin{array}{cc}
P_{1} & x \\
y & P_{2}
\end{array}\right] .
$$

By construction, we have $P_{1} \gtrdot x \gtrdot P_{2} \gtrdot y \gtrdot P_{1}$. This is a contradiction.
Thus at least $2 n-1$ cells cannot be good. This proves the bound.
₪ Proof using König's theorem, from Ankan Bhattacharya. This proof is based on the following additional claim:
Claim - No column/row can be all-good, and no transversal can be all-good.

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}$ ).
This claim alone is enough to imply the desired bound.
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.

Proof. Follows by König'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.

Suppose $a \leq \frac{n}{2} \leq b$; the other case is similar. Now we bound:
- The $a \times b$ cells of the claim are given to be all non-good.
- In the $n-a=b-1$ remaining rows, there is at least one more non-good cell.

Thus the number of non-good cells is at least
$$
a b+(b-1)=(a+1) b-1 \geq 2 \cdot n-1=n^{2}-(n-1)^{2},
$$
and so there are at most $(n-1)^{2}$ good cells.