2023 USAMO Problems/Problem 5
Contents
[hide]Problem
Let be an integer. We say that an arrangement of the numbers , , , in a 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 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 .
Proof that primes work
Suppose is prime. Then, let the arithmetic progressions in the th row have least term and common difference . For each cell with integer , assign a monomial . The sum of the monomials is where the LHS is obtained by summing over all cells and the RHS is obtained by summing over all rows. Let be the set of th roots of unity that are not ; then, the LHS of the above equivalence vanishes over and the RHS is Reducing the exponents (mod ) in the above expression yields when . Note that is a factor of , and as has degree less than , is either identically 0 or .
- If is identically 0, then never divides . Thus, no two elements in each row are congruent , so all residues are represented in each row. Now we can rearrange the grid so that column consists of all numbers , which works.
- If , then always divides . It is clear that each must be , so each row represents a single residue . Thus, we can rearrange the grid so that column contains all consecutive numbers from to , which works.
All in all, any prime satisfies the hypotheses of the problem.
Proof that composites do not work
Let . Look at the term ; 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 , then must also be in its column, which is impossible. If the column has difference , then no element in the next row can be in its column. If the common difference is , then and , 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 (Problems • Resources) | ||
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.