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

\begin{document}
\title{JMO 2024/4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 142}
\maketitle

\section*{Problem}
Let $n \geq 3$ be an integer.
Rowan and Colin play a game on an $n \times n$ grid of squares,
where each square is colored either red or blue.
Rowan is allowed to permute the rows of the grid and
Colin is allowed to permute the columns.
A grid coloring is orderly if:
\begin{itemize}
  \ii no matter how Rowan permutes the rows of the coloring,
  Colin can then permute the columns to restore the original grid coloring; and
  \ii no matter how Colin permutes the columns of the coloring,
  Rowan can then permute the rows to restore the original grid coloring.
\end{itemize}
In terms of $n$, how many orderly colorings are there?

\section*{Video}
\href{https://www.youtube.com/watch?v=s_bUukq7HiA&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/s\_bUukq7HiA}}

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

\newpage

\section*{Solution}
The answer is $2n!+2$.
In fact, we can describe all the orderly colorings as follows:
\begin{itemize}
  \ii The all-blue coloring.
  \ii The all-red coloring.
  \ii Each of the $n!$ colorings where every row/column has exactly one red cell.
  \ii Each of the $n!$ colorings where every row/column has exactly one blue cell.
\end{itemize}
These obviously work; we turn our attention to proving these are the only ones.

For the other direction, fix a orderly coloring $\mathcal A$.

Consider any particular column $C$ in $\mathcal A$
and let $m$ denote the number of red cells that $C$ has.
Any row permutation (say $\sigma$) that Rowan chooses will transform $C$ into
some column $\sigma(C)$, and our assumption requires $\sigma(C)$
has to appear somewhere in the original assignment $\mathcal A$.
An example for $n = 7$, $m = 2$, and a random $\sigma$ is shown below.

\begin{center}
\begin{asy}
  defaultpen(fontsize(14pt));
  pen bo = black + 1.4;
  filldraw(shift(0,0)*unitsquare, lightcyan, bo);
  filldraw(shift(0,1)*unitsquare, lightred, bo);
  filldraw(shift(0,2)*unitsquare, lightcyan, bo);
  filldraw(shift(0,3)*unitsquare, lightcyan, bo);
  filldraw(shift(0,4)*unitsquare, lightred, bo);
  filldraw(shift(0,5)*unitsquare, lightcyan, bo);
  filldraw(shift(0,6)*unitsquare, lightcyan, bo);
  label("$C$", (0.5,0), dir(-90));

  pen gr = deepgreen;
  real h = 8;
  draw((1,1.5)--(h,4.5), gr, EndArrow, Margins);
  draw((1,4.5)--(h,3.5), gr, EndArrow, Margins);
  draw((1,2.5)--(h,1.5), gr, EndArrow, Margins);
  draw((1,0.5)--(h,0.5), gr, EndArrow, Margins);
  draw((1,3.5)--(h,6.5), gr, EndArrow, Margins);
  draw((1,6.5)--(h,5.5), gr, EndArrow, Margins);
  draw((1,5.5)--(h,2.5), gr, EndArrow, Margins);

  filldraw(shift(h,0)*unitsquare, lightcyan, bo);
  filldraw(shift(h,1)*unitsquare, lightcyan, bo);
  filldraw(shift(h,2)*unitsquare, lightcyan, bo);
  filldraw(shift(h,3)*unitsquare, lightred, bo);
  filldraw(shift(h,4)*unitsquare, lightred, bo);
  filldraw(shift(h,5)*unitsquare, lightcyan, bo);
  filldraw(shift(h,6)*unitsquare, lightcyan, bo);
  label("$\sigma(C)$", (h+0.5,0), dir(-90));
  label("$\sigma$", ((1+h)/2, 0), dir(-90), gr);
\end{asy}
\end{center}

On the other hand, the number of possible patterns of $\sigma(C)$ is easily seen
to be exactly $\binom{n}{m}$ --- and they must all appear.
In particular, if $m \notin \{0, 1, n-1, n\}$,
then we immediately get a contradiction because $\mathcal A$ would need
too many columns (there are only $n$ columns in $\mathcal A$,
which is fewer than $\binom{n}{m}$).
Moreover, if either $m=1$ or $m=n-1$,
these columns are all the columns of $\mathcal A$;
these lead to the $2n!$ main cases we found before.

The only remaining case is when $m \in \{0,n\}$ for every column,
i.e.\ every column is monochromatic.
It's easy to see in that case the columns must all be the same color.

\end{document}
