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"
(finish solution 1)
Line 62: Line 62:
 
Now we split our proof into two cases.
 
Now we split our proof into two cases.
  
−
Case 1: <math>n</math> is odd.
+
Case 1: <math>n</math> is even.
  
 +
The largest integer less than <math>\frac{n-1}{2}</math> is <math>\frac{n}{2}-1</math>, so we know that:
  
 +
<math>{n \choose \frac{n}{2}}>{n \choose \frac{n}{2}-1}>\cdot\cdot\cdot>{n \choose 2}</math>
  
 +
by induction. On the other hand, the smallest integer greater than <math>\frac{n-1}{2}</math> is <math>\frac{n}{2}</math>, so we know that:
  
−
[INCOMPLETE]
+
<math>{n \choose \frac{n}{2}}>{n \choose \frac{n}{2}+1}>\cdot\cdot\cdot>{n \choose n-2}</math>
 +
 
 +
also by induction. Thus out of the given range for <math>m</math> we know that <math>{n \choose 2}</math> and <math>{n \choose n-2}</math> are the minimum values, and all that is left is to prove that they are both greater than <math>n</math>. Furthermore, since <math>{n \choose 2}={n \choose n-2}</math>, we only have to prove that <math>{n \choose 2}>n</math>.
 +
 
 +
We start with the given: <math>n>3</math>
 +
 
 +
<math>\Leftrightarrow</math> <math>\frac{n-1}{2}>1</math>
 +
 
 +
<math>\Leftrightarrow</math> <math>\frac{n(n-1)}{2}>n</math>
 +
 
 +
<math>\Leftrightarrow</math> <math>\frac{n!}{2!(n-2)!}>n</math>
 +
 
 +
<math>\Leftrightarrow</math> <math>{n \choose 2}>n</math>
 +
 
 +
Thus we have proven the inequality for all even <math>n</math>.
 +
 
 +
Case 2: <math>n</math> is odd.
 +
 
 +
The greatest integer less than <math>\frac{n-1}{2}</math> is <math>\frac{n-3}{2}</math>, so we know that:
 +
 
 +
<math>{n \choose \frac{n-1}{2}}>{n \choose \frac{n-3}{2}}>\cdot\cdot\cdot>{n \choose 2}</math>
 +
 
 +
by induction. On the other hand, the smallest integer greater than <math>\frac{n-1}{2}</math> is <math>\frac{n+1}{2}</math>, so we know that:
 +
 
 +
<math>{n \choose \frac{n+1}{2}}>{n \choose \frac{n+3}{2}}>\cdot\cdot\cdot>{n \choose n-2}</math>
 +
 
 +
also by induction. Since <math>{n \choose \frac{n+1}{2}}={n \choose \frac{n-1}{2}}</math>, we know that once again, <math>{n \choose n-2}={n \choose 2}</math> is the minimum of the given range for <math>m</math>, and the same proof applies. Thus, the inequality holds true for odd and in turn all positive integers <math>n>3</math>.
  
  

Revision as of 20:16, 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 even.

The largest integer less than $\frac{n-1}{2}$ is $\frac{n}{2}-1$, so we know that:

${n \choose \frac{n}{2}}>{n \choose \frac{n}{2}-1}>\cdot\cdot\cdot>{n \choose 2}$

by induction. On the other hand, the smallest integer greater than $\frac{n-1}{2}$ is $\frac{n}{2}$, so we know that:

${n \choose \frac{n}{2}}>{n \choose \frac{n}{2}+1}>\cdot\cdot\cdot>{n \choose n-2}$

also by induction. Thus out of the given range for $m$ we know that ${n \choose 2}$ and ${n \choose n-2}$ are the minimum values, and all that is left is to prove that they are both greater than $n$. Furthermore, since ${n \choose 2}={n \choose n-2}$, we only have to prove that ${n \choose 2}>n$.

We start with the given: $n>3$

$\Leftrightarrow$ $\frac{n-1}{2}>1$

$\Leftrightarrow$ $\frac{n(n-1)}{2}>n$

$\Leftrightarrow$ $\frac{n!}{2!(n-2)!}>n$

$\Leftrightarrow$ ${n \choose 2}>n$

Thus we have proven the inequality for all even $n$.

Case 2: $n$ is odd.

The greatest integer less than $\frac{n-1}{2}$ is $\frac{n-3}{2}$, so we know that:

${n \choose \frac{n-1}{2}}>{n \choose \frac{n-3}{2}}>\cdot\cdot\cdot>{n \choose 2}$

by induction. On the other hand, the smallest integer greater than $\frac{n-1}{2}$ is $\frac{n+1}{2}$, so we know that:

${n \choose \frac{n+1}{2}}>{n \choose \frac{n+3}{2}}>\cdot\cdot\cdot>{n \choose n-2}$

also by induction. Since ${n \choose \frac{n+1}{2}}={n \choose \frac{n-1}{2}}$, we know that once again, ${n \choose n-2}={n \choose 2}$ is the minimum of the given range for $m$, and the same proof applies. Thus, the inequality holds true for odd and in turn all positive integers $n>3$.


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=217499"