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
(→‎Another way to prove that \binom{n}{m}>n)
 
(34 intermediate revisions by 5 users not shown)
Line 1: Line 1:
−
Let <math>n \ge 3</math> be an integer. Rowan and Colin play a game on an <math>n \times n</math> 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 <math>orderly</math> if:
+
__TOC__
 +
 
 +
== Problem ==
 +
Let <math>n \ge 3</math> be an integer. Rowan and Colin play a game on an <math>n \times n</math> 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 <math>orderly</math> 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 Rowan permutes the rows of the coloring, Colin can then permute the columns to restore the original grid coloring; and
Line 6: Line 9:
  
 
In terms of <math>n</math>, how many orderly colorings are there?
 
In terms of <math>n</math>, how many orderly colorings are there?
 +
 +
== Solution 1 ==
 +
We focus on the leftmost column for simplicity. Let <math>m</math> be the number of red squares in this column. We then have five cases:
 +
 +
 +
1. <math>m=1</math>
 +
 +
When Rowan permutes the rows of the coloring, we consider only the first column, which by the above contains <math>m=1</math> red colors, so there are <math>{n \choose 1}=n</math> 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 <math>n\cdot (n-1)\cdot(n-2)\cdot\cdot\cdot2\cdot1=n!</math> 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. <math>m=n-1</math>
 +
 +
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 <math>n!</math> different colorings for this case.
 +
 +
 +
 +
3. <math>m=0</math>
 +
 +
Since we have an entirely blue column, we are unable to have a column with <math>1</math> 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 <math>0</math> as will be shown below, so there is <math>1</math> case here in which the entire coloring is red.
 +
 +
 +
 +
4. <math>m=n</math>
 +
 +
This is the same is an entire blue column, and, similar to above, we have <math>1</math> coloring.
 +
 +
 +
 +
5. <math>1<m<n-1</math>
 +
 +
This is the final case and is equivalent to permuting for <math>{n \choose m}</math> different ways. We must prove that this is greater than <math>n</math> to show that the columns are not able to contain every possible permutation of this column for all values of <math>n</math> such that <math>n>3</math> (when <math>n=3</math>, there is no such positive integer <math>m</math> 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 <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>.
 +
 +
<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 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:
 +
 +
<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>.
 +
 +
 +
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 <math>2\cdot n!+2</math> different colorings for which the above apply.
 +
 +
 +
~eevee9406
 +
 +
==Solution 2==
 +
Lemma 1: Each row and column must have the same number of red squares.
 +
 +
Proof: Suppose two rows do not have the same number of red squares. Suppose Rowan permutes the two rows onto each other. Then, because the two rows have a different number of red squares, there is no way for Colin to permute the columns, which permutes the squares in the row, to match the other row because the two rows have a different number of red squares. By a similar proof, the columns must have the same number of red squares as each other. Assume that each row has <math>m</math> red squares. Then, there are <math>nm</math> red squares in total. Because each column must have the same number of red squares as the other columns, the columns also must have <math>m</math> red squares each.
 +
 +
 +
Now, we want to find which values of <math>m</math> can produce a valid orderly coloring.
 +
 +
 +
Lemma: <math>C(n,k)>n</math> for <math>k\neq 0,1,n-1,n.</math> This is needed to prove the next lemma and is the most mathematical part of the solution.
 +
 +
Proof: Start with <math>C(n,1)=n.</math> Each time we increase <math>k</math> by <math>1</math> until <math>k=\lfloor0.5n\rfloor,</math> we are multiplying the previous value of <math>C(n,k)</math> by a fraction more than <math>1.\text{*}</math> Thus, <math>C(n,k)>n</math> for <math>2\le n \le \lfloor0.5n\rfloor.</math> Because <math>C(n,k)=C(n,n-k),</math> the lemma is proven for the rest of the conjectured values.
 +
 +
 +
Lemma 2: If <math>m\neq 0,1,n-1,n,</math> the coloring is not orderly.
 +
 +
Proof: Let's take a look at a particular column, where assume there are <math>2\le m\le n-2</math> red squares. When Rowan permutes the rows, the squares in this column have <math>C(n,m)</math> possible permutations. In order for Colin to be able permute the columns to return the grid to its original state, all of these <math>C(n,m)</math> permutations must be columns of the original grid. However, because there are only <math>n</math> columns. By the previous lemma, there are more permutations than columns, so the we are done.
 +
 +
 +
Lemma 3: If a permutation satisfies <math>m=0,1,n-1,n</math> and satisfies lemma <math>1,</math> it is orderly.
 +
 +
Proof: The <math>m=0,n</math> case is trivial: the grid never changes! For <math>m=1,n-1,</math> we only have to prove the <math>n=1</math> case because of symmetry: we can change red to blue and blue to red and it won't change the orderliness of the coloring as the overall arrangement of the different colors won't be changed. For the <math>m=1 case,</math> when Rowan permutes the rows, all of the columns will still be different columns of the original grid (as each column must have one red square, the rows of the red squares will be different) and can be permuted back to the original arrangement by Colin. Thus, this lemma is true.
 +
 +
 +
Finally, there is <math>1</math> coloring for the <math>m=0</math> case, and <math>n!</math> ways to permute the red squares to see which column values are assigned to the rows in the <math>m=1</math> case. There are similarly <math>n!</math> colorings for the <math>m=n-1</math> case, and <math>1</math> coloring for the <math>m=0</math> case. Thus, the answer is <math>\boxed{2n!+2}.</math>
 +
 +
 +
 +
<math>\text{*}</math> Specifically, <math>\frac{C(n,k)}{C(n,k-1)}=\frac{n-k+1}{k-1}</math> which is greater than <math>1</math> for <math>2\le n \le \lfloor0.5n\rfloor.</math>
 +
 +
 +
~BS2012
 +
 +
==Another way to prove that <math>\binom{n}{m}>n</math>==
 +
 +
Suppose we have <math>2\le{m}\le\lfloor{\frac{n}{2}}\rfloor</math>. Our goal is to show that
 +
 +
<cmath>\binom{n}{m}>n</cmath>
 +
 +
<cmath>\frac{n}{m}\cdot\frac{n-1}{m-1}\cdot\frac{n-2}{m-2}\cdots\frac{n-m+1}{1}>n</cmath>
 +
 +
<cmath>\frac{1}{m}\cdot\frac{n-1}{m-1}\cdot\frac{n-2}{m-2}\cdots\frac{n-m+1}{1}>1</cmath>
 +
 +
<cmath>\frac{n-1}{m-1}\cdot\frac{n-2}{m-2}\cdots\frac{n-m+1}{m}>1</cmath>.
 +
 +
Each of the above fractions is greater than one because <math>2\le{m}\le\lfloor{\frac{n}{2}}\rfloor</math>, so we are done.
 +
 +
~alexanderruan
 +
 +
==See Also==
 +
{{USAJMO newbox|year=2024|num-b=3|num-a=5}}
 +
{{MAA Notice}}

Latest revision as of 11:08, 10 May 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

Solution 2

Lemma 1: Each row and column must have the same number of red squares.

Proof: Suppose two rows do not have the same number of red squares. Suppose Rowan permutes the two rows onto each other. Then, because the two rows have a different number of red squares, there is no way for Colin to permute the columns, which permutes the squares in the row, to match the other row because the two rows have a different number of red squares. By a similar proof, the columns must have the same number of red squares as each other. Assume that each row has $m$ red squares. Then, there are $nm$ red squares in total. Because each column must have the same number of red squares as the other columns, the columns also must have $m$ red squares each.


Now, we want to find which values of $m$ can produce a valid orderly coloring.


Lemma: $C(n,k)>n$ for $k\neq 0,1,n-1,n.$ This is needed to prove the next lemma and is the most mathematical part of the solution.

Proof: Start with $C(n,1)=n.$ Each time we increase $k$ by $1$ until $k=\lfloor0.5n\rfloor,$ we are multiplying the previous value of $C(n,k)$ by a fraction more than $1.\text{*}$ Thus, $C(n,k)>n$ for $2\le n \le \lfloor0.5n\rfloor.$ Because $C(n,k)=C(n,n-k),$ the lemma is proven for the rest of the conjectured values.


Lemma 2: If $m\neq 0,1,n-1,n,$ the coloring is not orderly.

Proof: Let's take a look at a particular column, where assume there are $2\le m\le n-2$ red squares. When Rowan permutes the rows, the squares in this column have $C(n,m)$ possible permutations. In order for Colin to be able permute the columns to return the grid to its original state, all of these $C(n,m)$ permutations must be columns of the original grid. However, because there are only $n$ columns. By the previous lemma, there are more permutations than columns, so the we are done.


Lemma 3: If a permutation satisfies $m=0,1,n-1,n$ and satisfies lemma $1,$ it is orderly.

Proof: The $m=0,n$ case is trivial: the grid never changes! For $m=1,n-1,$ we only have to prove the $n=1$ case because of symmetry: we can change red to blue and blue to red and it won't change the orderliness of the coloring as the overall arrangement of the different colors won't be changed. For the $m=1 case,$ when Rowan permutes the rows, all of the columns will still be different columns of the original grid (as each column must have one red square, the rows of the red squares will be different) and can be permuted back to the original arrangement by Colin. Thus, this lemma is true.


Finally, there is $1$ coloring for the $m=0$ case, and $n!$ ways to permute the red squares to see which column values are assigned to the rows in the $m=1$ case. There are similarly $n!$ colorings for the $m=n-1$ case, and $1$ coloring for the $m=0$ case. Thus, the answer is $\boxed{2n!+2}.$


$\text{*}$ Specifically, $\frac{C(n,k)}{C(n,k-1)}=\frac{n-k+1}{k-1}$ which is greater than $1$ for $2\le n \le \lfloor0.5n\rfloor.$


~BS2012

Another way to prove that $\binom{n}{m}>n$

Suppose we have $2\le{m}\le\lfloor{\frac{n}{2}}\rfloor$. Our goal is to show that

\[\binom{n}{m}>n\]

\[\frac{n}{m}\cdot\frac{n-1}{m-1}\cdot\frac{n-2}{m-2}\cdots\frac{n-m+1}{1}>n\]

\[\frac{1}{m}\cdot\frac{n-1}{m-1}\cdot\frac{n-2}{m-2}\cdots\frac{n-m+1}{1}>1\]

\[\frac{n-1}{m-1}\cdot\frac{n-2}{m-2}\cdots\frac{n-m+1}{m}>1\].

Each of the above fractions is greater than one because $2\le{m}\le\lfloor{\frac{n}{2}}\rfloor$, so we are done.

~alexanderruan

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