\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$ axis-parallel 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}