2023 USAMO Problems/Problem 5

Problem

Let $n\geq3$ be an integer. We say that an arrangement of the numbers $1$, $2$, $\dots$, $n^2$ in a $n \times n$ table is row-valid if the numbers in each row can be permuted to form an arithmetic progression, and column-valid if the numbers in each column can be permuted to form an arithmetic progression. For what values of $n$ is it possible to transform any row-valid arrangement into a column-valid arrangement by permuting the numbers in each row?

Video Solution

https://www.youtube.com/watch?v=Fbs9ncZuwGM

Solution 1

The answer is all $\boxed{\text{prime } n}$.

Proof that primes work

Suppose $n=p$ is prime. Then, let the arithmetic progressions in the $i$th row have least term $a_i$ and common difference $d_i$. For each cell with integer $k$, assign a monomial $x^k$. The sum of the monomials is \[x(1+x+\ldots+x^{n^2-1}) = \sum_{i=1}^n x^{a_i}(1+x^{d_i}+\ldots+x^{(n-1)d_i}),\] where the LHS is obtained by summing over all cells and the RHS is obtained by summing over all rows. Let $S$ be the set of $p$th roots of unity that are not $1$; then, the LHS of the above equivalence vanishes over $S$ and the RHS is \[\sum_{p \mid d_i} x^{a_i}.\] Reducing the exponents (mod $p$) in the above expression yields \[f(x) := \sum_{p \mid d_i} x^{a_i \pmod{p}} = 0\] when $x \in S$. Note that $\prod_{s \in S} (x-s)=1+x+\ldots+x^{p-1}$ is a factor of $f(x)$, and as $f$ has degree less than $p$, $f$ is either identically 0 or $f(x)=1+x+\ldots+x^{p-1}$.

- If $f$ is identically 0, then $p$ never divides $d_i$. Thus, no two elements in each row are congruent $\pmod{p}$, so all residues are represented in each row. Now we can rearrange the grid so that column $i$ consists of all numbers $i \pmod{p}$, which works.

- If $f(x)=1+x+\ldots+x^{p-1}$, then $p$ always divides $d_i$. It is clear that each $d_i$ must be $p$, so each row represents a single residue $\pmod{p}$. Thus, we can rearrange the grid so that column $i$ contains all consecutive numbers from $1 + (i-1)p$ to $ip$, which works.


All in all, any prime $n$ satisfies the hypotheses of the problem.

Proof that composites do not work

Let $n=ab$. Look at the term $a^2b+ab$; we claim it cannot be part of a column that has cells forming an arithmetic sequence after any appropriate rearranging. After such a rearrangement, if the column it is in has common difference $d<ab=n$, then $a^2b+ab-d$ must also be in its column, which is impossible. If the column has difference $d > ab = n$, then no element in the next row can be in its column. If the common difference is $d = ab = n$, then $a^2b + ab - 2d = a^2b - ab$ and $a^2b + ab - d = a^2b$, which are both in the row above it, must both be in the same column, which is impossible. Therefore, the grid is not column-valid after any rearrangement, which completes the proof.

~ Leo.Euler

See Also

2023 USAMO (ProblemsResources)
Preceded by
Problem 4
Followed by
Problem 6
1 2 3 4 5 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png