Difference between revisions of "2023 USAMO Problems/Problem 5"
(→Solution 1) |
(→Proof that composites do not work) |
||
(2 intermediate revisions by 2 users not shown) | |||
Line 21: | Line 21: | ||
===Proof that composites do not work=== | ===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 | + | 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 | ~ Leo.Euler | ||
+ | |||
+ | ==See Also== | ||
+ | {{USAMO newbox|year=2023|num-b=4|num-a=6}} | ||
+ | {{MAA Notice}} |
Latest revision as of 21:07, 11 February 2024
Contents
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.