Difference between revisions of "2024 USAJMO Problems/Problem 2"
(Created page with "__TOC__ === 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\leq2...") |
m (sign) |
||
(9 intermediate revisions by 5 users not shown) | |||
Line 2: | Line 2: | ||
=== Problem === | === 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. | + | 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 == | + | === 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}} |
Latest revision as of 22:07, 15 July 2024
Contents
Problem
Let and
be positive integers. Let
be the set of integer points
with
and
. A configuration of
rectangles is called happy if each point in
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 . For the purpose of notation, we will group the points in
into
rows and
columns and refer to them as such accordingly.
Base Case
Consider the case where . 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
We can evaluate the parity of this expression by expanding the factorials:
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 .
Inductive Step
Assume that there are an odd number of happy configurations for some and
. We will now prove that there must also be an odd number of happy configurations for
and
.
Consider for
and
. Denote the rightmost two columns of
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 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 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 .
First of all, because each vertex in a rectangle shares a column with another vertex and because the strip is only two columns wide, 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 must lie on rows which each contain only one other point inside of the strip. This forces the existence of another rectangle
which has exactly two vertices in the strip and has vertices lying on the same two rows as
. Then, it must be possible to create a new happy configuration
by swapping the vertices of
and
which in the strip between the two rectangles.
Notice that repeating this procedure on the new happy configuration results in again. As a result, there exists a one-to-one pairing between happy configurations for which such a rectangle
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 and
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 for any positive integer
and
.
Note: It is possible to reduce the base case to because the inductive step can be applied to incrementing
as well.
- pomme_de_terre_
See Also
2024 USAJMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.