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 "1996 USAMO Problems/Problem 6"

(Created page with "==Problem== Determine (with proof) whether there is a subset <math>X</math> of the integers with the following property: for any integer <math>n</math> there is exactly one so...")
 
m (→‎Solution)
 
(3 intermediate revisions by 2 users not shown)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
Start with an incomplete subset <math>S = (S_1, S_2, S_3, ... S_m)</math>, such that for any integer n, there is exactly zero or one solutions to <math>a + 2b = n</math> with <math>a,b \in S</math>. Let <math>N</math> be the smallest integer such that for any <math>S_i</math>, <math>|S_i| < N</math>. Note that <math>|S_i+2S_j| < 3N</math> for any <math>S_i</math> and <math>S_j</math>
 +
 
 +
 
 +
Suppose <math>M</math> is the smallest non-negative integer without a solution in <math>S</math> yet. Clearly, <math>0 \le M \le 3N</math>. Generate <math>S_{m+1}</math> and <math>S_{m+2}</math> such that <math>S_{m+1} = -10N - M</math>, and <math>S_{m+2} = 5N + M</math>. Thus, we now have the solution <math>S_{m+1}+2S_{m+2} = M</math>.
 +
 
 +
''Note: The values 10 and 5 can be replaced by any sufficiently large values such that the first is twice the second.''
 +
 
 +
 
 +
Now, we must prove that the addition of these two terms to <math>S</math> does not result in an integer n that has two solutions. Of course, <math>S_{m+1} + 2S_{m+2} = M</math> which previously had no solutions. Furthermore, <math>S_{m+1} + 2S_{m+2} = -15N - M</math>.
 +
 
 +
:For any <math>S_i</math>, <math>-12N - M < S_{m+1}+2S_i < -8N-M</math>, and <math>-21N - 2M < S_i+2S_{m+1} < -19N - 2M</math>.
 +
 
 +
::Since <math>0 \le M \le 3N</math>, we get that  <math>-18N < S_{m+1}+2S_i < -8N</math> and <math>-27N < S_i+2S_{m+1} < -19N</math>
 +
 
 +
:Similarly, <math>3N + M < S_{m+2}+2S_i < 5N + M</math>, and <math>9N+2M < S_i+2S_{m+2} < 11N+2M</math>.
 +
 
 +
::Since <math>0 \le M \le 3N</math>, we get that  <math>3N < S_{m+2}+2S_i < 8N</math> and <math>9N < S_i+2S_{m+2} < 17N</math>.
 +
 
 +
Since all of these sums (other than <math>M</math>) are either greater than <math>3N</math> or less than <math>-3N</math>, they are all sums that previously had no solutions. Furthermore, none of these sums are duplicated, as sums of different forms are contained in disjoint ranges of integers.
 +
 
 +
Thus, we have proved that we can generate a subset <math>S</math> such that all non-negative integers n have a unique solution <math>a + 2b = n</math>.
 +
 
 +
 
 +
For negative integers M that have no solutions in <math>S</math> a similar proof holds, but instead generating the terms <math>S_{m+1} = 10N - M</math> and <math>S_{m+2} = -5N + M</math>.
 +
 
 +
 
 +
For any integer M that currently has no solution in S, we can always add two terms <math>S_{m+1}</math> and <math>S_{m+2}</math> such that <math>S_{m+1} + 2S_{m+2} = M</math> that do not result in duplicated sums.
 +
 
 +
Thus, there does exist a subset <math>X</math> of the integers such that for any integer <math>n</math> there is exactly one solution to <math>a + 2b = n</math> with <math>a, b \in X</math>.
  
 
==See Also==
 
==See Also==
−
 
+
{{USAMO newbox|year=1996|num-b=5|after=Last Problem}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 06:56, 16 April 2018

Problem

Determine (with proof) whether there is a subset $X$ of the integers with the following property: for any integer $n$ there is exactly one solution of $a + 2b = n$ with $a,b \in X$.

Solution

Start with an incomplete subset $S = (S_1, S_2, S_3, ... S_m)$, such that for any integer n, there is exactly zero or one solutions to $a + 2b = n$ with $a,b \in S$. Let $N$ be the smallest integer such that for any $S_i$, $|S_i| < N$. Note that $|S_i+2S_j| < 3N$ for any $S_i$ and $S_j$


Suppose $M$ is the smallest non-negative integer without a solution in $S$ yet. Clearly, $0 \le M \le 3N$. Generate $S_{m+1}$ and $S_{m+2}$ such that $S_{m+1} = -10N - M$, and $S_{m+2} = 5N + M$. Thus, we now have the solution $S_{m+1}+2S_{m+2} = M$.

Note: The values 10 and 5 can be replaced by any sufficiently large values such that the first is twice the second.


Now, we must prove that the addition of these two terms to $S$ does not result in an integer n that has two solutions. Of course, $S_{m+1} + 2S_{m+2} = M$ which previously had no solutions. Furthermore, $S_{m+1} + 2S_{m+2} = -15N - M$.

For any $S_i$, $-12N - M < S_{m+1}+2S_i < -8N-M$, and $-21N - 2M < S_i+2S_{m+1} < -19N - 2M$.
Since $0 \le M \le 3N$, we get that $-18N < S_{m+1}+2S_i < -8N$ and $-27N < S_i+2S_{m+1} < -19N$
Similarly, $3N + M < S_{m+2}+2S_i < 5N + M$, and $9N+2M < S_i+2S_{m+2} < 11N+2M$.
Since $0 \le M \le 3N$, we get that $3N < S_{m+2}+2S_i < 8N$ and $9N < S_i+2S_{m+2} < 17N$.

Since all of these sums (other than $M$) are either greater than $3N$ or less than $-3N$, they are all sums that previously had no solutions. Furthermore, none of these sums are duplicated, as sums of different forms are contained in disjoint ranges of integers.

Thus, we have proved that we can generate a subset $S$ such that all non-negative integers n have a unique solution $a + 2b = n$.


For negative integers M that have no solutions in $S$ a similar proof holds, but instead generating the terms $S_{m+1} = 10N - M$ and $S_{m+2} = -5N + M$.


For any integer M that currently has no solution in S, we can always add two terms $S_{m+1}$ and $S_{m+2}$ such that $S_{m+1} + 2S_{m+2} = M$ that do not result in duplicated sums.

Thus, there does exist a subset $X$ of the integers such that for any integer $n$ there is exactly one solution to $a + 2b = n$ with $a, b \in X$.

See Also

1996 USAMO (Problems • Resources)
Preceded by
Problem 5 		Followed by
Last Problem
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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1996_USAMO_Problems/Problem_6&oldid=93981"