Difference between revisions of "2025 USAJMO Problems/Problem 3"

Latest revision as of 17:14, 23 March 2025

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

@@ Line 11: / Line 11: @@
 == Solution ==
-{{solution}}
+We claim the answer is <math>\boxed{\binom{m+n}{m}^2}</math>. Color <math>\mathcal R</math> in a black-and-white checkerboard pattern such that the lower left square is black. Suppose an up-right path <math>P</math> splits <math>\mathcal R</math> into two subsets <math>S</math> and <math>S'</math> such that <math>S</math> is below <math>P</math>. Call a subset balanced if there are an equal number of black and white squares.
+Claim 1: <math>S</math> and <math>S'</math> are tileable iff <math>S</math> is balanced.
+Proof: Since <math>\mathcal R</math> itself is balanced and rotating it by <math>180^\circ</math> swaps <math>S</math> and <math>S'</math>, it suffices to only consider <math>S</math>. Note that dominoes each cover exactly one black and one white square, so <math>S</math> being tileable implies <math>S</math> is balanced.
+We will proceed with the converse by attempting to remove a domino from <math>S</math> such that <math>S</math> can still be traced by a new up-right path. Indeed, so long as <math>P</math> contains a sequence of <math>\uparrow\rightarrow\rightarrow</math> or <math>\uparrow\uparrow\rightarrow</math>, we can replace these with <math>\rightarrow\rightarrow\uparrow</math> and <math>\rightarrow\uparrow\uparrow</math>, 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 <math>P</math> forms a staircase and remains on the upper or left edges of <math>\mathcal R</math> for at most one edge each. However, we can trivially observe that <math>S</math> is then unbalanced, since if the largest diagonal in <math>S</math> has <math>k</math> squares (which must be of the same color), <math>k+(k-2)+\cdots>(k-1)+(k-3)+\cdots</math>. <math>\square</math>
+Assign coordinates to the gridline intersections such that the lower left corner is <math>(0,0)</math> and the upper right is <math>(2m,2n)</math>. Assign each <math>\rightarrow</math> move with starting point <math>(x,y)</math> a two-letter designation, where the first letter is <math>o</math> or <math>e</math> depending on the parity of <math>x+y</math> and the second letter depends on the parity of <math>x</math>. (I blame this naming system on leo; he was making some really weird sounds :P)
+Claim 2: <math>S</math> is balanced iff there are an equal number of <math>\rightarrow</math>'s with starting letter <math>o</math> and <math>e</math>.
+Proof: Consider <math>S</math> as a union of multiple columns of squares, each topped with a <math>\rightarrow</math>. Upon inspection, <math>oe</math>'s give one more black square than white square, while <math>eo</math>'s give one more white square. There are an even number of squares, and therefore equal number of black and white squares, under an <math>oo</math> or <math>ee</math>. Thus, for <math>S</math> to be balanced, there must be an equal number of <math>oe</math>'s and <math>eo</math>'s; but since there are also an equal number of odd-numbered and even-numbered columns, we must have <math>oe+ee=eo+oo</math>, so <math>ee=oo</math> and <math>oe+oo=eo+ee</math>, as desired. Reversing the logic gives the converse. <math>\square</math>
+We finish by splitting moves into two sets based on the parity of <math>x+y</math> and then ordering <math>m~\rightarrow</math>'s amongst the <math>m+n</math> moves in each set, giving the desired <math>\tbinom{m+n}{m}^2</math> paths. <math>\square</math>
+~rhydon516
 ==See Also==
+https://artofproblemsolving.com/community/c5h3531394p34326818
 {{USAJMO newbox|year=2025|num-b=2|num-a=4}}
 {{MAA Notice}}

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

Difference between revisions of "2025 USAJMO Problems/Problem 3"

Latest revision as of 17:14, 23 March 2025

Contents

Problem

Solution

See Also