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

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

\section*{Problem}
Let $m$ and $n$ be positive integers.
Let $S$ be the set of lattice points $(x,y)$ with $1 \le x \le 2m$ and $1 \le y \le 2n$.
A configuration of $mn$ rectangles is called \emph{happy} if each point of $S$
is the vertex of exactly one rectangle.
Prove that the number of happy configurations is odd.

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

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

\newpage

\section*{Solution}
There are several possible approaches to the problem;
most of them involve pairing some of the happy configurations in various ways,
leaving only a few configurations which remain fixed.
We present the original proposer's solution and Evan's more complicated one.

\paragraph{Original proposer's solution.}
To this end, let's denote by $f(2m, 2n)$ the number of happy configurations
for a $2m \times 2n$ grid of lattice points
(not necessarily equally spaced --- this doesn't change the count).
We already have the following easy case.
\begin{claim*}
  We have $f(2, 2n) = (2n-1)!{!} = (2n-1) \cdot (2n-3) \cdot \dots \cdot 3 \cdot 1$.
\end{claim*}
\begin{proof}
  The top row is the top edge of some rectangle and there are $2n-1$ choices
  for the bottom edge of that rectangle.
  It then follows $f(2, 2n) = (2n-1) \cdot f(2, 2n-2)$
  and the conclusion follows by induction on $n$, with $f(2,2) = 1$.
\end{proof}

We will prove that:
\begin{claim*}
  Assume $m,n \ge 1$. When $f(2m, 2n) \equiv f(2m-2, 2n) \pmod 2$.
\end{claim*}
\begin{proof}
  Given a happy configuration $\mathcal C$, let $\tau(\mathcal C)$
  be the happy configuration obtained by swapping the last two columns.
  Obviously $\tau(\tau(\mathcal C)) = \mathcal C$ for every happy $\mathcal C$.
  So in general, we can consider two different kinds of configurations $\mathcal C$,
  those for which $\tau(\mathcal C) \neq \mathcal C$,
  so we get pairs $\{\mathcal C, \tau(\mathcal C)\}$,
  and those with $\tau(\mathcal C) = \mathcal C$.

  Now configurations fixed by $\tau$ can be described readily:
  this occurs if and only if the last two columns are self-contained,
  meaning every rectangle with a vertex in these columns is
  completely contained in these two columns.
  \begin{center}
  \begin{asy}
    real eps = 0.6;
    filldraw(box((8.4, 0.4), (10.6, 8.6)), opacity(0.2)+yellow, black+dashed);
    for (int x=1; x<=10; ++x) {
      for (int y=1; y<=8; ++y) {
        pair P = (x,y);
        if (x==9 || x==10) { fill(circle(P, 0.1), blue); }
        else { dot(P); }
      }
    }
    draw((9,0.3)..(9.5,-0.2)..(10,0.3), deepgreen+1.2, Arrows(TeXHead));
    label("$\tau$", (9.5,-0.2), dir(-90), deepgreen);
    label("$f(2,2n)$", (9.5,8.6), dir(90), black);
    label("$f(2m-2,2n)$", (4.5,8.6), dir(90), black);
    draw((0.8,8.4)--(0.8,8.6)--(8.2,8.6)--(8.2,8.4), grey);
  \end{asy}
  \end{center}
  Hence it follows that
  \[ f(2m, 2n) = 2 (\text{number of pairs}) + f(2m-2, 2n) \cdot f(2, 2n). \]
  Taking modulo $2$ gives the result.
\end{proof}
By the same token $f(2m, 2n) \equiv f(2m, 2n-2) \pmod 2$.
So all $f$-values have the same parity, and from $f(2,2)=1$ we're done.

\begin{remark*}
  There are many variations of the solution using different kinds of $\tau$.
  The solution with $\tau$ swapping two rows seems to be the simplest.
\end{remark*}

\paragraph{Evan's permutation-based solution.}
Retain the notation $f(2m, 2n)$ from before.
Given a happy configuration, consider all the rectangles
whose left edge is in the first column.
Highlight every column containing the right edge of such a rectangle.
For example, in the figure below, there are two highlighted columns.
(The rectangles are drawn crooked so one can tell them apart.)
\begin{center}
\begin{asy}
  real eps = 0.6;
  for (int x=1; x<=10; ++x) {
    for (int y=1; y<=6; ++y) {
      pair P = (x,y);
      dot(P);
    }
  }
  dotfactor *= 1;
  real eps = 0.3;
  void rect(real a, real b, real u, real v, pen p) {
    draw( (a,b)--((a+u)/2, b-eps)--(u,b)--(u+eps,(b+v)/2)--(u,v)
      --((a+u)/2, v+eps)--(a,v)--(a-eps, (b+v)/2)--cycle, p);
    fill(circle((a,b), 0.2), p);
    fill(circle((u,b), 0.2), p);
    fill(circle((a,v), 0.2), p);
    fill(circle((u,v), 0.2), p);
  }

  rect(1,1,8,3, blue + 1.5);
  rect(1,2,5,6, deepgreen + 1.5);
  rect(1,4,8,5, red + 1.5);

  filldraw(box((4.5, 0.6), (5.5, 6.4)), opacity(0.2)+yellow, black+dashed);
  filldraw(box((7.5, 0.6), (8.5, 6.4)), opacity(0.2)+yellow, black+dashed);
\end{asy}
\end{center}
We organize happy configurations based on the set of highlighted columns.
Specifically, define the relation $\sim$ on configurations by saying that
$\mathcal C \sim \mathcal C'$ if they differ by any permutation of the highlighted columns.
This is an equivalence relation.
And in general, if there are $k$ highlighted columns,
its equivalence class under $\sim$ has $k!$ elements.

Then
\begin{claim*}
  $f(2m, 2n)$ has the same parity as the number of happy configurations
  with \emph{exactly} one highlighted column.
\end{claim*}
\begin{proof}
  Since $k!$ is even for all $k \ge 2$, but odd when $k=1$.
\end{proof}

There are $2m-1$ ways to pick a single highlighted column,
and then $f(2, 2n) = (2n-1){!}{!}$ ways to use the left column and highlighted column.
So the count in the claim is exactly given by
\[ (2m-1) \cdot (2n-1){!}{!} f(2m-2, 2n). \]
This implies $f(2m, 2n) \equiv f(2m-2,2n) \pmod 2$
and proceeding by induction as before solves the problem.

\end{document}
