Problem: Let $n \ge 2$ be a fixed integer. The cells of an $n \times n$ table are
filled with the integers from $1$ to $n^2$ with each number appearing exactly once.
Let $N$ be the number of unordered quadruples of cells on this board
which form an axis-aligned rectangle,
with the two smaller integers being on opposite vertices of this rectangle.
Find the largest possible value of $N$.

\end{enumerate}

Solution: The largest possible value of $N$ is $\tfrac1{12}n^2(n^2-1)$.
Call these rectangles \emph{wobbly}.
We defer the construction until the proof is complete,
since the proof suggests the construction.

\paragraph{Proof of bound.}
Call a triple of integers $(a,b,c)$ an \emph{elbow}
if $a$ and $b$ are in the same row, $b$ and $c$ are in the same column,
and $a < b > c$.
Observe that the wobbly rectangles are exactly the ones with $2$ elbows.
\begin{claim*}
  Every axis-aligned rectangle has at least $1$ elbow.
\end{claim*}
\begin{proof}
  The smallest integer in any rectangle is the center of an elbow.
\end{proof}
\begin{remark*}
  In fact, it is true that any rectangle must have exactly $1$ or $2$ elbows.
  However, this fact is not needed in the proof.
\end{remark*}
Let $E$ be the number of elbows and $M$ be the number of non-wobbly rectangles.
Then, the number of elbows is at least $M + 2N = \tbinom n2^2 + N$, so
\[ E \ge \binom n2^2 + N \iff N \le E - \binom n2^2. \]

To this end, we will provide an upper bound on $E$.
For each cell $c$, define:
\begin{itemize}
  \ii $f(c)$ to be the number of cells in $c$'s row which are smaller than $c$, and
  \ii $g(c)$ to be the number of cells in $c$'s column which are smaller than $c$.
\end{itemize}
Then, the number of elbows centered at $c$ equals $f(c) g(c)$.
Thus, the number of elbows satisfies
\begin{align*}
  E &= \sum_c f(c) g(c) \\
  &\le \sum_c \frac12 \big[f(c)^2 + g(c)^2] \\
  &= n(0^2 + \dots + (n-1)^2) \\
  &= \frac{n^2(n-1)(2n-1)}{6}.
\end{align*}
It follows that the number of wobbly rectangles satisfies
\begin{align*}
  N &\le E - \binom n2^2 \\
  &\le \frac{n^2(n-1)(2n-1)}6 - \frac{n^2(n-1)^2}4 \\
  &= \frac{n^2(n^2-1)}{12}
\end{align*}
as desired.

\paragraph{Construction.}
From the proof above, equality holds if and only if $f(c) = g(c)$ everywhere.

Select any $n \times n$ Latin square on symbols $0$, \dots, $n-1$,
and replace the $n$ copies of symbol $k$ with the integers $kn + 1$, \dots, $kn + n$ in some order.
This construction is valid, because for each cell $c$,
$f(c)$ and $g(c)$ both equal the symbol originally placed in $c$.

Here is an example for $n = 6$.
The left grid is the Latin square,
and the right grid is one possible table that can be derived from it.
\begin{center}
  \begin{asy}
    unitsize(24);
    defaultpen(fontsize(14pt));
    pen[] colors = {palered, mediumyellow, lightgreen, lightcyan, paleblue, pink};
    int n = colors.length;
    transform t0 = shift(-0.5, -0.5);
    transform t1 = scale(1, -1);
    transform t2 = shift(n+2, 0) * t1;

    for (int i = 0; i < n; ++i)
       for (int j = 0; j < n; ++j) {
          int k = (i-j) % n;
          fill(t1 * t0 * shift(i, j) * unitsquare, colors[k]);
          fill(t2 * t0 * shift(i, j) * unitsquare, colors[k]);
          label((string) k, t1 * (i, j));
          label((string) (n*k + j + 1), t2 * (i, j));
    }

    for (int i = 0; i <= n; ++i) {
       draw(t1 * t0 * ((i, 0)--(i, n) ^^ (0, i)--(n, i)), gray(0.6));
       draw(t2 * t0 * ((i, 0)--(i, n) ^^ (0, i)--(n, i)), gray(0.6));
    }
  \end{asy}
\end{center}

\begin{remark*}[Structure of optimal tables]
  In fact, any optimal table must lead to a Latin square in a similar way,
  by reversing the above idea: replace each cell $c$ with $f(c) = g(c)$.

  This suggests how to construct all optimal tables:
  choose any Latin square on $0$, \dots, $n-1$,
  and fill in the cells so that the relative order of cells in every row and column is preserved.
\end{remark*}

\begin{remark*}
  If the grid is filled out in a random order,
  the expected number of wobbly rectangles is $\frac{1}{12}n^2(n-1)^2$.
  This is asymptotically equal to the maximum value.
\end{remark*}