Difference between revisions of "2023 USAMO Problems/Problem 5"

Latest revision as of 20:07, 11 February 2024

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

@@ Line 21: / Line 21: @@
 ===Proof that composites do not work===
-Look at the term <math>a^2b+ab</math>; we claim it cannot be part of a column that has cells forming an arithmetic sequence after any appropriate rearranging. After such a rearrangment, if the column it is in has common difference <math>d<ab=n</math>, then <math>a^2+ab-d</math> must also be in its column, which is impossible. If the column has difference <math>d > ab = n</math>, then no element in the next row can be in its column. If the common difference is <math>d = ab = n</math>, then <math>a^2b + ab - 2d = a^2b - ab</math> and <math>a^2 + ab - d = a^2b</math>, 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.
+Let <math>n=ab</math>. Look at the term <math>a^2b+ab</math>; 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 <math>d<ab=n</math>, then <math>a^2b+ab-d</math> must also be in its column, which is impossible. If the column has difference <math>d > ab = n</math>, then no element in the next row can be in its column. If the common difference is <math>d = ab = n</math>, then <math>a^2b + ab - 2d = a^2b - ab</math> and <math>a^2b + ab - d = a^2b</math>, 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

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

Page

Toolbox

Search