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 8: / Line 8: @@
 ==Solution 1==
+The answer is all <math>\boxed{\text{prime } n}</math>.
 ===Proof that primes work===
-The answer is all prime <math>n</math>.
-Proof that prime <math>n</math> work: Suppose <math>n=p</math> is prime. Then, let the arithmetic progressions in the <math>i</math>th row have least term <math>a_i</math> and common difference <math>d_i</math>. For each cell with integer <math>k</math>, assign a monomial <math>x^k</math>. The sum of the monomials is <cmath> 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}), </cmath> where the LHS is obtained by summing over all cells and the RHS is obtained by summing over all rows. Let <math>S</math> be the set of <math>p</math>th roots of unity that are not <math>1</math>; then, the LHS of the above equivalence vanishes over <math>S</math> and the RHS is <cmath> \sum_{p \mid d_i} x^{a_i}. </cmath> Reducing the exponents (mod <math>p</math>) in the above expression  yields <cmath> f(x) := \sum_{p \mid d_i} x^{a_i \pmod{p}} = 0 </cmath> when <math>x \in S</math>. Note that <math>\prod_{s \in S} (x-s)=1+x+\ldots+x^{p-1}</math> is a factor of <math>f(x)</math>, and as <math>f</math> has degree less than <math>p</math>, <math>f</math> is either identically 0 or <math>f(x)=1+x+\ldots+x^{p-1}</math>.
+Suppose <math>n=p</math> is prime. Then, let the arithmetic progressions in the <math>i</math>th row have least term <math>a_i</math> and common difference <math>d_i</math>. For each cell with integer <math>k</math>, assign a monomial <math>x^k</math>. The sum of the monomials is <cmath> 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}), </cmath> where the LHS is obtained by summing over all cells and the RHS is obtained by summing over all rows. Let <math>S</math> be the set of <math>p</math>th roots of unity that are not <math>1</math>; then, the LHS of the above equivalence vanishes over <math>S</math> and the RHS is <cmath> \sum_{p \mid d_i} x^{a_i}. </cmath> Reducing the exponents (mod <math>p</math>) in the above expression  yields <cmath> f(x) := \sum_{p \mid d_i} x^{a_i \pmod{p}} = 0 </cmath> when <math>x \in S</math>. Note that <math>\prod_{s \in S} (x-s)=1+x+\ldots+x^{p-1}</math> is a factor of <math>f(x)</math>, and as <math>f</math> has degree less than <math>p</math>, <math>f</math> is either identically 0 or <math>f(x)=1+x+\ldots+x^{p-1}</math>.
 - If <math>f</math> is identically 0, then <math>p</math> never divides <math>d_i</math>. Thus, no two elements in each row are congruent <math>\pmod{p}</math>, so all residues are represented in each row. Now we can rearrange the grid so that column <math>i</math> consists of all numbers <math>i \pmod{p}</math>, which works.
@@ Line 22: / 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 its 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
+==See Also==
+{{USAMO newbox|year=2023|num-b=4|num-a=6}}
+{{MAA Notice}}

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