2024 USAJMO Problems/Problem 4

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 that ${n \choose m}>n$ .

Proof:

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

2024 USAJMO (Problems • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search

2024 USAJMO Problems/Problem 4

Contents

Problem

Solution 1

See Also