Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2004 USAMO Problems/Problem 2"

(patch)
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:
  
−
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>.
  
−
(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.
  
−
[b]Lemma:[/b] If <math>x,y\in a_i</math>, then <math>ax + by\in S</math> for integers <math>a,b</math>.
+
'''Lemma:''' If <math>x,y\in a_i</math>, then <math>ax + by\in S</math> for integers <math>a,b</math>.
−
[b]Proof:[/b] 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>.
+
 
 +
'''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 13:23, 17 July 2014

Problem

(Kiran Kedlaya) Suppose $a_1, \dots, a_n$ are integers whose greatest common divisor is 1. Let $S$ be a set of integers with the following properties:

(a) For $i = 1, \dots, n$, $a_i \in S$.

(b) For $i,j = 1, \dots, n$ (not necessarily distinct), $a_i - a_j \in S$.

(c) For any integers $x,y \in S$, if $x + y \in S$, then $x - y \in S$.

Prove that $S$ must be equal to the set of all integers.

Solution

Suppose $a_i$ has only one element; then for the greatest common divisor to be 1, $1$ has to be the sole element. Then $1$ is in $S$ by (a), $0$ is in $S$ by (b), $0 + 1 = 1\in S\Rightarrow 0 - 1 = - 1\in S$ by (c), and we can apply (c) analogously to get that $n\cdot 1 \in S$ for integers $n$ and hence $S$ is the set of all integers, as desired.

Lemma: If $x,y\in a_i$, then $ax + by\in S$ for integers $a,b$.

Proof: Assume $a_i$ has at least two elements; $x$ and $y$. By (b), $x - y$ is in $S$, and by the application of (c) above, we get that $n(x - y)$ for integers $n$ is in $S$. Then apply (c) to $n(x - y)$ and $ny$ or $nx$ to get that $ax + by\in S$ for all $a,b\in \mathbb{Z}$.

Now let the terms be $a_1,a_2,\ldots,a_{n}$. By applying our lemma many times, all numbers in the form $\sum c_1a_1$ for a sequence of integers $c_i$ 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 $S$.

By Schur's theorem (a generalization of the more well-known Chicken McNugget theorem), every integer greater than some integer $n$ is attainable, and hence there are two members of $S$ in the form $\sum c_1a_1$ which are consecutive integers. Furthermore, because such numbers are closed under addition, their sum is in $S$, and hence so is their difference; $1$. Thus, by the argument at the beginning at this proof, $S$ 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2004_USAMO_Problems/Problem_2&oldid=62537"