Difference between revisions of "2004 USAMO Problems/Problem 2"
(patch) |
5849206328x (talk | contribs) m (→Problem: author) |
||
(2 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
+ | (''Kiran Kedlaya'') Suppose <math>a_1, \dots, a_n</math> are integers whose greatest common divisor is 1. Let <math>S</math> be a set of integers with the following properties: | ||
− | + | (a) For <math>i = 1, \dots, n</math>, <math>a_i \in S</math>. | |
− | |||
(b) For <math>i,j = 1, \dots, n</math> (not necessarily distinct), <math>a_i - a_j \in S</math>. | (b) For <math>i,j = 1, \dots, n</math> (not necessarily distinct), <math>a_i - a_j \in S</math>. | ||
+ | |||
(c) For any integers <math>x,y \in S</math>, if <math>x + y \in S</math>, then <math>x - y \in S</math>. | (c) For any integers <math>x,y \in S</math>, if <math>x + y \in S</math>, then <math>x - y \in S</math>. | ||
Line 12: | Line 13: | ||
Suppose <math>a_i</math> has only one element; then for the greatest common divisor to be 1, <math>1</math> has to be the sole element. Then <math>1</math> is in <math>S</math> by (a), <math>0</math> is in <math>S</math> by (b), <math>0 + 1 = 1\in S\Rightarrow 0 - 1 = - 1\in S</math> by (c), and we can apply (c) analogously to get that <math>n\cdot 1 \in S</math> for integers <math>n</math> and hence <math>S</math> is the set of all integers, as desired. | Suppose <math>a_i</math> has only one element; then for the greatest common divisor to be 1, <math>1</math> has to be the sole element. Then <math>1</math> is in <math>S</math> by (a), <math>0</math> is in <math>S</math> by (b), <math>0 + 1 = 1\in S\Rightarrow 0 - 1 = - 1\in S</math> by (c), and we can apply (c) analogously to get that <math>n\cdot 1 \in S</math> for integers <math>n</math> and hence <math>S</math> is the set of all integers, as desired. | ||
− | + | '''Lemma:''' If <math>x,y\in a_i</math>, then <math>ax + by\in S</math> for integers <math>a,b</math>. | |
− | + | ||
+ | '''Proof:''' Assume <math>a_i</math> has at least two elements; <math>x</math> and <math>y</math>. By (b), <math>x - y</math> is in <math>S</math>, and by the application of (c) above, we get that <math>n(x - y)</math> for integers <math>n</math> is in <math>S</math>. Then apply (c) to <math>n(x - y)</math> and <math>ny</math> or <math>nx</math> to get that <math>ax + by\in S</math> for all <math>a,b\in \mathbb{Z}</math>. | ||
Now let the terms be <math>a_1,a_2,\ldots,a_{n}</math>. By applying our lemma many times, all numbers in the form <math>\sum c_1a_1</math> for a sequence of integers <math>c_i</math> 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 <math>S</math>. | Now let the terms be <math>a_1,a_2,\ldots,a_{n}</math>. By applying our lemma many times, all numbers in the form <math>\sum c_1a_1</math> for a sequence of integers <math>c_i</math> 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 <math>S</math>. | ||
Line 25: | Line 27: | ||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 14:23, 17 July 2014
Problem
(Kiran Kedlaya) 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) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
- <url>viewtopic.php?p=17440 Discussion on AoPS/MathLinks</url>
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.