2024 USAJMO Problems/Problem 2
Contents
[hide]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.