Difference between revisions of "1992 USAMO Problems/Problem 3"
m (→Resources) |
Danielguo94 (talk | contribs) m (→Solution) |
||
Line 23: | Line 23: | ||
Assume that the lemma is true for some <math>n</math>, then <math>2^n</math> is not expressible with the <math>n</math>-<math>p</math> set. Thus, when we add an element to the end to from a <math>n+1</math>-<math>r</math> set, <math>a_{n+1}</math> must be <math>\le p+1</math> if we want <math>r>p</math> because we need a way to express <math>p+1</math>. Since <math>p+1</math> is not expressible by the first <math>n</math> elements, <math>p+1+a_{n+1}</math> is not expressible by these <math>n+1</math> elements. Thus, the new set is a <math>n+1</math>-<math>r</math> set, where <math>r\le p+1+a_{n+1}\le2^{n+1}-1</math> | Assume that the lemma is true for some <math>n</math>, then <math>2^n</math> is not expressible with the <math>n</math>-<math>p</math> set. Thus, when we add an element to the end to from a <math>n+1</math>-<math>r</math> set, <math>a_{n+1}</math> must be <math>\le p+1</math> if we want <math>r>p</math> because we need a way to express <math>p+1</math>. Since <math>p+1</math> is not expressible by the first <math>n</math> elements, <math>p+1+a_{n+1}</math> is not expressible by these <math>n+1</math> elements. Thus, the new set is a <math>n+1</math>-<math>r</math> set, where <math>r\le p+1+a_{n+1}\le2^{n+1}-1</math> | ||
− | <b> | + | <b>Lemma Proven</b> |
<br/> | <br/> |
Revision as of 00:51, 13 April 2012
Problem
For a nonempty set of integers, let be the sum of the elements of . Suppose that is a set of positive integers with and that, for each positive integer , there is a subset of for which . What is the smallest possible value of ?
Solution
Let's a - set be a set such that , where , , , and for each , , , , .
(For Example is a - set and is a - set)
Futhermore, let call a - set a - good set if , and a - bad set if (note that for any - set. Thus, we can ignore the case where ).
Futhermore, if you add any amount of elements to the end of a - bad set to form another - set (with a different ), it will stay as a - bad set because for any positive integer and $\nexist \sigma(Y)=p+1$ (Error compiling LaTeX. Unknown error_msg).
Lemma) If is a - set, .
For , or because and .
Assume that the lemma is true for some , then is not expressible with the - set. Thus, when we add an element to the end to from a - set, must be if we want because we need a way to express . Since is not expressible by the first elements, is not expressible by these elements. Thus, the new set is a - set, where
Lemma Proven
The answer to this question is .
The following set is a - set:
Note that the first 8 numbers are power of from to , and realize that any or less digit binary number is basically sum of a combination of the first elements in the set. Thus, $\exist Y\subseteq\{1,2,4,8,16,32,64,128\}$ (Error compiling LaTeX. Unknown error_msg), .
which implies that $\exist A\subseteq\{1,2,4,8,16,32,64,128,247\}$ (Error compiling LaTeX. Unknown error_msg), .
Simlarly $\exist B\subseteq\{1,2,4,8,16,32,64,128,247,248\}$ (Error compiling LaTeX. Unknown error_msg), and $\exist C\subseteq\{1,2,4,8,16,32,64,128,247,248,750\}$ (Error compiling LaTeX. Unknown error_msg), .
Thus, is a - set.
Now, let's assume for contradiction that such that $\left {a_i}\right|_{1\le i\le11}$ (Error compiling LaTeX. Unknown error_msg) is a - set where
$\left {a_i}\right|_{1\le i\le8}$ (Error compiling LaTeX. Unknown error_msg) is a - set where (lemma).
Let $\left {a_i}\right|_{1\le i\le10}$ (Error compiling LaTeX. Unknown error_msg) be a - set where the first elements are the same as the previous set. Then, is not expressible as . Thus, .
In order to create a - set with and the first elements being the ones on the previous set, because we need to make expressible as . Note that is not expressible, thus .
Done but not elegant...
Resources
1992 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |