2004 USAMO Problems/Problem 2
From AoPSWiki
Problem
Suppose 
are integers whose greatest common divisor is 1. Let 
be a set of integers with the following properties:
(a) For 
, 
.
(b) For 
(not necessarily distinct), 
.
(c) For any integers 
, if 
, then 
.
Prove that must be equal to the set of all integers.
Solution
Suppose 
has only one element; then for the greatest common divisor to be 1, 
has to be the sole element. Then is in by (a), 
is in by (b), 
by (c), and we can apply (c) analogously to get that 
for integers 
and hence is the set of all integers, as desired.
Lemma: If 
, then 
for integers 
.
Proof: Assume has at least two elements; 
and 
. By (b), 
is in , and by the application of (c) above, we get that 
for integers is in . Then apply (c) to and 
or 
to get that for all 
.
Now let the terms be 
. By applying our lemma many times, all numbers in the form 
for a sequence of integers 
are attainable if the sequence is of a length which is a power of 2. If not, we "pad" the sequence with many copies of an existing element of the sequence until it does have a length which is a power of 2 - it is apparent that this will not change .
By Schur's theorem (a generalization of the more well-known Chicken McNugget theorem), every integer greater than some integer is attainable, and hence there are two members of in the form which are consecutive integers. Furthermore, because such numbers are closed under addition, their sum is in , and hence so is their difference; . Thus, by the argument at the beginning at this proof, is the set of all integers, as desired.
Resources
| 2004 USAMO (Problems • Resources: AoPS | ML) | ||
| Preceded by Problem 1 | 1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 3 |
