Difference between revisions of "2024 USAJMO Problems/Problem 2"

Latest revision as of 21:07, 15 July 2024

Let $m$ and $n$ be positive integers. Let $S$ be the set of integer points $(x,y)$ with $1\leq x\leq2m$ and $1\leq y\leq2n$ . 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.

Solution 1

We will proceed by induction on $n$ . For the purpose of notation, we will group the points in $S$ into $m$ rows and $n$ columns and refer to them as such accordingly.

Base Case

Consider the case where $n=1$ . It is clear that any rectangle in the happy configuration is determined only by which two rows its vertices lie on, and that these two rows are automatically filled by the vertices of the rectangle. By repeatedly picking two rows to form a new rectangle from the remaining rows, the number of rectangles in this case is

$\frac{1}{m!}\prod_{k=1}^{m}\binom{2k}{2}=\frac{1}{m!}\binom{2m}{2}\binom{2m-2}{2}\cdots\binom{2}{2}=\frac{(2m)!}{m!\cdot2^m}$

We can evaluate the parity of this expression by expanding the factorials:

$\frac{(2m)(2m-1)(2m-2)\cdots(2)(1)}{(2m)(2m-2)\cdots(2)}=(2m-1)(2m-3)\cdots(1)$

Since none of the factors are even, this expression must be odd. As a result, there are always an odd number of happy configurations if $n=1$ .

Inductive Step

Assume that there are an odd number of happy configurations for some $m$ and $n$ . We will now prove that there must also be an odd number of happy configurations for $m$ and $n+1$ .

Consider $S$ for $m$ and $n+1$ . Denote the rightmost two columns of $S$ as the "strip".

Case 1: All rectangles in the happy configuration lie entirely within the strip or entirely outside of the strip.

By the inductive hypothesis, there are an odd number of happy configurations in the region of $S$ outside of the strip. Additionally, by the base case, there are an odd number of happy configurations in the strip. Since no rectangles extend between the two regions, the number of happy configurations in this case is just the product of the two values, which is clearly odd.

Case 2: There exists a rectangle $R$ which contains some vertices inside of the strip and some vertices outside of the strip.

Let a happy configuration with this property be denoted as $H$ .

First of all, because each vertex in a rectangle shares a column with another vertex and because the strip is only two columns wide, $R$ must have exactly two vertices in the strip. Furthermore, the two vertices in the strip must lie in the same column, and the same applies for the two vertices outside of the strip.

Notice that both vertices of $R$ must lie on rows which each contain only one other point inside of the strip. This forces the existence of another rectangle $R'$ which has exactly two vertices in the strip and has vertices lying on the same two rows as $R$ . Then, it must be possible to create a new happy configuration $H'$ by swapping the vertices of $R$ and $R_1$ which in the strip between the two rectangles.

Notice that repeating this procedure on the new happy configuration results in $H$ again. As a result, there exists a one-to-one pairing between happy configurations for which such a rectangle $R$ exists.

However, the existence of such a pairing implies that the number of happy configurations in this case is even.

Conclusion:

The number of happy configurations for $m$ and $n+1$ is the sum of the number of happy configurations from each of the two cases. Since there are an odd number of happy configurations in case 1 and an even number of happy configurations in case 2, there must be an odd total number of happy configurations.

By induction, there must be an odd number of happy configurations of $S$ for any positive integer $m$ and $n$ .

Note: It is possible to reduce the base case to $m=n=1$ because the inductive step can be applied to incrementing $m$ as well.

- pomme_de_terre_

@@ Line 2: / Line 2: @@
 === Problem ===
 Let <math>m</math> and <math>n</math> be positive integers. Let <math>S</math> be the set of integer points <math>(x,y)</math> with <math>1\leq x\leq2m</math> and <math>1\leq y\leq2n</math>. A configuration of <math>mn</math> rectangles is called ''happy'' if each point in <math>S</math> 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.
+=== Solution 1 ===
+We will proceed by induction on <math>n</math>. For the purpose of notation, we will group the points in <math>S</math> into <math>m</math> rows and <math>n</math> columns and refer to them as such accordingly.
+'''Base Case'''
+Consider the case where <math>n=1</math>. It is clear that any rectangle in the happy configuration is determined only by which two rows its vertices lie on, and that these two rows are automatically filled by the vertices of the rectangle. By repeatedly picking two rows to form a new rectangle from the remaining rows, the number of rectangles in this case is
+<cmath>\frac{1}{m!}\prod_{k=1}^{m}\binom{2k}{2}=\frac{1}{m!}\binom{2m}{2}\binom{2m-2}{2}\cdots\binom{2}{2}=\frac{(2m)!}{m!\cdot2^m}</cmath>
+We can evaluate the parity of this expression by expanding the factorials:
+<cmath>\frac{(2m)(2m-1)(2m-2)\cdots(2)(1)}{(2m)(2m-2)\cdots(2)}=(2m-1)(2m-3)\cdots(1)</cmath>
+Since none of the factors are even, this expression must be odd. As a result, there are always an odd number of happy configurations if <math>n=1</math>.
+'''Inductive Step'''
+Assume that there are an odd number of happy configurations for some <math>m</math> and <math>n</math>. We will now prove that there must also be an odd number of happy configurations for <math>m</math> and <math>n+1</math>.
+Consider <math>S</math> for <math>m</math> and <math>n+1</math>. Denote the rightmost two columns of <math>S</math> as the "strip".
+Case 1: All rectangles in the happy configuration lie entirely within the strip or entirely outside of the strip.
+By the inductive hypothesis, there are an odd number of happy configurations in the region of <math>S</math> outside of the strip. Additionally, by the base case, there are an odd number of happy configurations in the strip. Since no rectangles extend between the two regions, the number of happy configurations in this case is just the product of the two values, which is clearly odd.
+Case 2: There exists a rectangle <math>R</math> which contains some vertices inside of the strip and some vertices outside of the strip.
+Let a happy configuration with this property be denoted as <math>H</math>.
+First of all, because each vertex in a rectangle shares a column with another vertex and because the strip is only two columns wide, <math>R</math> must have exactly two vertices in the strip. Furthermore, the two vertices in the strip must lie in the same column, and the same applies for the two vertices outside of the strip.
+Notice that both vertices of <math>R</math> must lie on rows which each contain only one other point inside of the strip. This forces the existence of another rectangle <math>R'</math> which has exactly two vertices in the strip and has vertices lying on the same two rows as <math>R</math>. Then, it must be possible to create a new happy configuration <math>H'</math> by swapping the vertices of <math>R</math> and <math>R_1</math> which in the strip between the two rectangles.
+Notice that repeating this procedure on the new happy configuration results in <math>H</math> again. As a result, there exists a one-to-one pairing between happy configurations for which such a rectangle <math>R</math> exists.
+However, the existence of such a pairing implies that the number of happy configurations in this case is even.
+Conclusion:
+The number of happy configurations for <math>m</math> and <math>n+1</math> is the sum of the number of happy configurations from each of the two cases. Since there are an odd number of happy configurations in case 1 and an even number of happy configurations in case 2, there must be an odd total number of happy configurations.
+By induction, there must be an odd number of happy configurations of <math>S</math> for any positive integer <math>m</math> and <math>n</math>.
+Note: It is possible to reduce the base case to <math>m=n=1</math> because the inductive step can be applied to incrementing <math>m</math> as well.
+- pomme_de_terre_
 ==See Also==
 {{USAJMO newbox|year=2024|num-b=1|num-a=3}}
 {{MAA Notice}}

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

Page

Toolbox

Search

Difference between revisions of "2024 USAJMO Problems/Problem 2"

Latest revision as of 21:07, 15 July 2024

Contents

Problem

Solution 1

See Also