Problem

Source: USAJMO 2024/2

Tags: AMC, USA(J)MO, USAJMO, xtimmyGgettingflamed



Let $m$ and $n$ be positive integers. Let $S$ be the set of integer points $(x,y)$ with $1\leq x\leq 2m$ and $1\leq y\leq 2n$. A configuration of $mn$ rectangles is called happy if each point in $S$ is a vertex of exactly one rectangle, and all rectangles have sides parallel to the coordinate axes. Prove that the number of happy configurations is odd. Proposed by Serena An and Claire Zhang