2024 USAJMO Problems/Problem 4
Problem
Let be an integer. Rowan and Colin play a game on an 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 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 , how many orderly colorings are there?
Solution 1
We focus on the leftmost column for simplicity. Let be the number of red squares in this column. We then have five cases:
1.
When Rowan permutes the rows of the coloring, we consider only the first column, which by the above contains red colors, so there are 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 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.
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 different colorings for this case.
3.
Since we have an entirely blue column, we are unable to have a column with 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 as will be shown below, so there is case here in which the entire coloring is red.
4.
This is the same is an entire blue column, and, similar to above, we have coloring.
5.
This is the final case and is equivalent to permuting for different ways. We must prove that this is greater than to show that the columns are not able to contain every possible permutation of this column for all values of such that (when , there is no such positive integer 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 and are positive integers such that and , it is true for all and that .
Proof: Assume that .
Similarly, we can prove that for .
Now we split our proof into two cases.
Case 1: is even.
The largest integer less than is , so we know that:
by induction. On the other hand, the smallest integer greater than is , so we know that:
also by induction. Thus out of the given range for we know that and are the minimum values, and all that is left is to prove that they are both greater than . Furthermore, since , we only have to prove that .
We start with the given:
Thus we have proven the inequality for all even .
Case 2: is odd.
The greatest integer less than is , so we know that:
by induction. On the other hand, the smallest integer greater than is , so we know that:
also by induction. Since , we know that once again, is the minimum of the given range for , and the same proof applies. Thus, the inequality holds true for odd and in turn all positive integers .
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 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 red squares. Then, there are red squares in total. Because each column must have the same number of red squares as the other columns, the columns also must have red squares each.
Now, we want to find which values of can produce a valid orderly coloring.
Lemma: for This is needed to prove the next lemma and is the most mathematical part of the solution.
Proof: Start with Each time we increase by until we are multiplying the previous value of by a fraction more than Thus, for Because the lemma is proven for the rest of the conjectured values.
Lemma 2: If the coloring is not orderly.
Proof: Let's take a look at a particular column, where assume there are red squares. When Rowan permutes the rows, the squares in this column have possible permutations. In order for Colin to be able permute the columns to return the grid to its original state, all of these permutations must be columns of the original grid. However, because there are only columns. By the previous lemma, there are more permutations than columns, so the we are done.
Lemma 3: If a permutation satisfies and satisfies lemma it is orderly.
Proof: The case is trivial: the grid never changes! For we only have to prove the 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 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 coloring for the case, and ways to permute the red squares to see which column values are assigned to the rows in the case. There are similarly colorings for the case, and coloring for the case. Thus, the answer is
Specifically, which is greater than for
~BS2012
Another way to prove that
Suppose we have . Our goal is to show that
.
Each of the above fractions is greater than one because , 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.