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 4"

m
Line 46: Line 46:
  
  
−
Lemma: Given that <math>m</math> and <math>n</math> are positive integers such that <math>1<m<n-1</math> and <math>n>3</math>, it is true that <math>{n \choose m}>n</math>.
+
Lemma: Given that <math>m</math> and <math>n</math> are positive integers such that <math>1<m<n-1</math> and <math>n>3</math>, it is true for all <math>m</math> and <math>n</math> that <math>{n \choose m}>n</math>.
  
 +
Proof: Assume that <math>m<\frac{n-1}{2}</math>.
  
−
Proof:
+
<math>\Leftrightarrow</math> <math>m+1<n-m</math>
  
 +
<math>\Leftrightarrow</math> <math>(m+1)!(n-m-1)!<m!(n-m)!</math>
 +
 +
<math>\Leftrightarrow</math> <math>\frac{n!}{m!(n-m)!}<\frac{n!}{(m+1)!(n-m-1)!}</math>
 +
 +
<math>\Leftrightarrow</math> <math>{n \choose m}<{n \choose m+1}</math>
 +
 +
Similarly, we can prove that <math>{n \choose m}>{n \choose m+1}</math> for <math>m>\frac{n-1}{2}</math>.
 +
 +
Now we split our proof into two cases.
 +
 +
Case 1: <math>n</math> is odd.
 +
 +
 +
 +
 +
[INCOMPLETE]
  
  

Revision as of 10:21, 27 March 2024

Problem

Let $n \ge 3$ be an integer. Rowan and Colin play a game on an $n \times n$ grid of squares, where each square is colored either red or blue. Rowan is allowed to permute the rows of the grid, and Colin is allowed to permute the columns of the grid. A grid coloring is $orderly$ if:

  • no matter how Rowan permutes the rows of the coloring, Colin can then permute the columns to restore the original grid coloring; and
  • no matter how Colin permutes the column of the coloring, Rowan can then permute the rows to restore the original grid coloring;

In terms of $n$, how many orderly colorings are there?

Solution 1

We focus on the leftmost column for simplicity. Let $m$ be the number of red squares in this column. We then have five cases:


1. $m=1$

When Rowan permutes the rows of the coloring, we consider only the first column, which by the above contains $m=1$ red colors, so there are ${n \choose 1}=n$ ways to permute the first column’s rows. Thus every other column will have to contain one different permutation of the first column; otherwise, there will be at least one permutation of which there is no corresponding column.


Furthermore, each permutation will be different, so each row will contain one and only one red square, which also fulfills the case of if Colin permutes the coloring first. Thus there are $n\cdot (n-1)\cdot(n-2)\cdot\cdot\cdot2\cdot1=n!$ different colorings for this case (the same as choosing squares such as no square is in the same row or column as any other square).


2. $m=n-1$

This is essentially the same as case 1 except for the coloring; now there is one blue square and the rest are red squares. Thus there are also $n!$ different colorings for this case.


3. $m=0$

Since we have an entirely blue column, we are unable to have a column with $1$ red square only as doing so would leave one permutation that is not covered by at least one column (that space is being taken for the blank column). We are also unable to have a completely blue column as doing so would allow for Colin to shift the columns and in doing so fail for Rowan to shift back the columns. We also cannot have a column with any other number of red squares other than $0$ as will be shown below, so there is $1$ case here in which the entire coloring is red.


4. $m=n$

This is the same is an entire blue column, and, similar to above, we have $1$ coloring.


5. $1<m<n-1$

This is the final case and is equivalent to permuting for ${n \choose m}$ different ways. We must prove that this is greater than $n$ to show that the columns are not able to contain every possible permutation of this column for all values of $n$ such that $n>3$ (when $n=3$, there is no such positive integer $m$ that satisfies the conditions). Note that if we have any column with a different number of red squares, it is an unattainable column and is thus not optimal.


Lemma: Given that $m$ and $n$ are positive integers such that $1<m<n-1$ and $n>3$, it is true for all $m$ and $n$ that ${n \choose m}>n$.

Proof: Assume that $m<\frac{n-1}{2}$.

$\Leftrightarrow$ $m+1<n-m$

$\Leftrightarrow$ $(m+1)!(n-m-1)!<m!(n-m)!$

$\Leftrightarrow$ $\frac{n!}{m!(n-m)!}<\frac{n!}{(m+1)!(n-m-1)!}$

$\Leftrightarrow$ ${n \choose m}<{n \choose m+1}$

Similarly, we can prove that ${n \choose m}>{n \choose m+1}$ for $m>\frac{n-1}{2}$.

Now we split our proof into two cases.

Case 1: $n$ is odd.



[INCOMPLETE]


As a result, due to our lemma, there are always more permutations of the columns than the number of columns itself, so there will always exist a permutation of the column such that there are no corresponding original columns of which to match with. Thus there are no solutions for this case.


In conclusion, there are a total of $2\cdot n!+2$ different colorings for which the above apply.


~eevee9406

See Also

2024 USAJMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
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_4&oldid=217483"