Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(Solution)
m (sign)
 
(2 intermediate revisions by the same user not shown)
Line 7: Line 7:
  
 
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.
 
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'''
 
'''Base Case'''
Line 20: Line 21:
 
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>.
 
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```
+
 
 +
'''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>.
 
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> be the "strip".
+
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.
 
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.
 
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.
 
Case 2: There exists a rectangle <math>R</math> which contains some vertices inside of the strip and some vertices outside of the strip.
Line 41: Line 45:
  
 
However, the existence of such a pairing implies that the number of happy configurations in this case is even.
 
However, the existence of such a pairing implies that the number of happy configurations in this case is even.
 +
  
 
Conclusion:
 
Conclusion:
Line 47: Line 52:
  
 
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>.
 
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.
 
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==
 
==See Also==
 
{{USAJMO newbox|year=2024|num-b=1|num-a=3}}
 
{{USAJMO newbox|year=2024|num-b=1|num-a=3}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 21:07, 15 July 2024

Problem

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_

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_USAJMO_Problems/Problem_2&oldid=222695"