# 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?

## 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, 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