2025 USAJMO Problems/Problem 3

Problem

Let $m$ and $n$ be positive integers, and let $\mathcal R$ be a $2m\times 2n$ grid of unit squares.

A domino is a $1\times2$ or $2\times1$ rectangle. A subset $S$ of grid squares in $\mathcal R$ is domino-tileable if dominoes can be placed to cover every square of $S$ exactly once with no domino extending outside of $S$ . Note: The empty set is domino tileable.

An up-right path is a path from the lower-left corner of $\mathcal R$ to the upper-right corner of $\mathcal R$ formed by exactly $2m+2n$ edges of the grid squares.

Determine, with proof, in terms of $m$ and $n$ , the number of up-right paths that divide $\mathcal R$ into two domino-tileable subsets.

Solution

We claim the answer is $\boxed{\binom{m+n}{m}^2}$ . Color $\mathcal R$ in a black-and-white checkerboard pattern such that the lower left square is black. Suppose an up-right path $P$ splits $\mathcal R$ into two subsets $S$ and $S'$ such that $S$ is below $P$ . Call a subset balanced if there are an equal number of black and white squares.

Claim 1: $S$ and $S'$ are tileable iff $S$ is balanced.

Proof: Since $\mathcal R$ itself is balanced and rotating it by $180^\circ$ swaps $S$ and $S'$ , it suffices to only consider $S$ . Note that dominoes each cover exactly one black and one white square, so $S$ being tileable implies $S$ is balanced.

We will proceed with the converse by attempting to remove a domino from $S$ such that $S$ can still be traced by a new up-right path. Indeed, so long as $P$ contains a sequence of $\uparrow\rightarrow\rightarrow$ or $\uparrow\uparrow\rightarrow$ , we can replace these with $\rightarrow\rightarrow\uparrow$ and $\rightarrow\uparrow\uparrow$ , respectively, and effectively remove a domino (this also preserves balanced-ness). Repeating this until we reach the empty set suffices, as we can reconstruct using the sequence of domino removal. The only cases where this fails is when $P$ forms a staircase and remains on the upper or left edges of $\mathcal R$ for at most one edge each. However, we can trivially observe that $S$ is then unbalanced, since if the largest diagonal in $S$ has $k$ squares (which must be of the same color), $k+(k-2)+\cdots>(k-1)+(k-3)+\cdots$ . $\square$

Assign coordinates to the gridline intersections such that the lower left corner is $(0,0)$ and the upper right is $(2m,2n)$ . Assign each $\rightarrow$ move with starting point $(x,y)$ a two-letter designation, where the first letter is $o$ or $e$ depending on the parity of $x+y$ and the second letter depends on the parity of $x$ . (I blame this naming system on leo; he was making some really weird sounds :P)

Claim 2: $S$ is balanced iff there are an equal number of $\rightarrow$ 's with starting letter $o$ and $e$ .

Proof: Consider $S$ as a union of multiple columns of squares, each topped with a $\rightarrow$ . Upon inspection, $oe$ 's give one more black square than white square, while $eo$ 's give one more white square. There are an even number of squares, and therefore equal number of black and white squares, under an $oo$ or $ee$ . Thus, for $S$ to be balanced, there must be an equal number of $oe$ 's and $eo$ 's; but since there are also an equal number of odd-numbered and even-numbered columns, we must have $oe+ee=eo+oo$ , so $ee=oo$ and $oe+oo=eo+ee$ , as desired. Reversing the logic gives the converse. $\square$

We finish by splitting moves into two sets based on the parity of $x+y$ and then ordering $m~\rightarrow$ 's amongst the $m+n$ moves in each set, giving the desired $\tbinom{m+n}{m}^2$ paths. $\square$

~rhydon516

2025 USAJMO (Problems • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search

2025 USAJMO Problems/Problem 3

Contents

Problem

Solution

See Also