Difference between revisions of "1992 USAMO Problems/Problem 3"
(→Solution) |
m |
||
Line 1: | Line 1: | ||
+ | == Problem == | ||
+ | |||
For a nonempty set <math>S</math> of integers, let <math>\sigma(S)</math> be the sum of the elements of <math>S</math>. Suppose that <math>A = \{a_1, a_2, \ldots, a_{11}\}</math> is a set of positive integers with <math>a_1 < a_2 < \cdots < a_{11}</math> and that, for each positive integer <math>n \le 1500</math>, there is a subset <math>S</math> of <math>A</math> for which <math>\sigma(S) = n</math>. What is the smallest possible value of <math>a_{10}</math>? | For a nonempty set <math>S</math> of integers, let <math>\sigma(S)</math> be the sum of the elements of <math>S</math>. Suppose that <math>A = \{a_1, a_2, \ldots, a_{11}\}</math> is a set of positive integers with <math>a_1 < a_2 < \cdots < a_{11}</math> and that, for each positive integer <math>n \le 1500</math>, there is a subset <math>S</math> of <math>A</math> for which <math>\sigma(S) = n</math>. What is the smallest possible value of <math>a_{10}</math>? | ||
Revision as of 10:41, 22 April 2010
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
Lemms 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 |