Difference between revisions of "1996 USAMO Problems/Problem 6"
Coolboykid66 (talk | contribs) (→Solution) |
Coolboykid66 (talk | contribs) m (→Solution) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 24: | Line 24: | ||
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>. | 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 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>. | ||
| Line 30: | Line 31: | ||
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. | 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 | + | 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== | ||
Latest revision as of 06:56, 16 April 2018
Problem
Determine (with proof) whether there is a subset 
of the integers with the following property: for any integer 
there is exactly one solution of 
with 
.
Solution
Start with an incomplete subset 
, such that for any integer n, there is exactly zero or one solutions to with 
. Let 
be the smallest integer such that for any 
, 
. Note that 
for any and 
Suppose 
is the smallest non-negative integer without a solution in 
yet. Clearly, 
. Generate 
and 
such that 
, and 
. Thus, we now have the solution 
.
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 does not result in an integer n that has two solutions. Of course, 
which previously had no solutions. Furthermore, 
.
- For any
, 
, and 
.
, and 
.- Since
, we get that 
and 
- Since
and 
- Similarly,
, and 
.
, and 
.- Since , we get that
and 
.
- Since
and 
.Since all of these sums (other than ) are either greater than 
or less than 
, 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 such that all non-negative integers n have a unique solution .
For negative integers M that have no solutions in a similar proof holds, but instead generating the terms 
and 
.
For any integer M that currently has no solution in S, we can always add two terms and such that that do not result in duplicated sums.
Thus, there does exist a subset of the integers such that for any integer there is exactly one solution to with 
.
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. 
