Difference between revisions of "1992 USAMO Problems/Problem 3"
m |
m (→Resources) |
||
(5 intermediate revisions by 5 users not shown) | |||
Line 10: | Line 10: | ||
<br/> | <br/> | ||
− | + | Furthermore, let call a <math>n</math>-<math>p</math> set a <math>n</math>-<math>p</math> good set if <math>a_n\le p</math>, and a <math>n</math>-<math>p</math> bad set if <math>a_n\ge p+1</math> (note that <math>\nexists \sigma(Y)=p+1</math> for any <math>n</math>-<math>p</math> set. Thus, we can ignore the case where <math>a_n=p+1</math>). | |
<br/> | <br/> | ||
− | + | Furthermore, if you add any amount of elements to the end of a <math>n</math>-<math>p</math> bad set to form another <math>n</math>-<math>p</math> set (with a different <math>n</math>), it will stay as a <math>n</math>-<math>p</math> bad set because <math>a_{n+x}>a_{n}>p+1</math> for any positive integer <math>x</math> and <math>\nexists \sigma(Y)=p+1</math>. | |
<br/> | <br/> | ||
− | <b>Lemma</b>) If <math>Z</math> is a <math>n</math>-<math>p</math> set, <math>p\ | + | <b>Lemma</b>) If <math>Z</math> is a <math>n</math>-<math>p</math> set, <math>p\leq 2^n-1</math>. |
<br/> | <br/> | ||
For <math>n=1</math>, <math>p=0</math> or <math>1</math> because <math>a_1=1 \rightarrow p=1</math> and <math>a_1\ne1\rightarrow p=0</math>. | For <math>n=1</math>, <math>p=0</math> or <math>1</math> because <math>a_1=1 \rightarrow p=1</math> and <math>a_1\ne1\rightarrow p=0</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\ | + | 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\leq p+1+a_{n+1} \leq 2^{n+1}-1</math> |
− | <b> | + | <b>Lemma Proven</b> |
<br/> | <br/> | ||
Line 32: | Line 32: | ||
<math>\{1,2,4,8,16,32,64,128,247,248,750\}</math> | <math>\{1,2,4,8,16,32,64,128,247,248,750\}</math> | ||
− | Note that the first 8 numbers are power of <math>2</math> from <math>0</math> to <math>7</math>, and realize that any <math>8</math> or less digit binary number is basically sum of a combination of the first <math>8</math> elements in the set. Thus, <math>\ | + | Note that the first 8 numbers are power of <math>2</math> from <math>0</math> to <math>7</math>, and realize that any <math>8</math> or less digit binary number is basically sum of a combination of the first <math>8</math> elements in the set. Thus, <math>\exists Y\subseteq\{1,2,4,8,16,32,64,128\}</math>, <math>\sigma(Y)=x \forall 1\le x\leq 255</math>. |
− | <math>248\le\sigma(y)+a_9\le502</math> which implies that <math>\ | + | <math>248\le\sigma(y)+a_9\le502</math> which implies that <math>\exists A\subseteq\{1,2,4,8,16,32,64,128,247\}</math>, <math>\sigma(A)=x \forall 1\le x\leq 502</math>. |
− | + | Similarly <math>\exists B\subseteq\{1,2,4,8,16,32,64,128,247,248\}</math>, <math>\sigma(A)=x \forall 1\le x\le750</math> and <math>\exists C\subseteq\{1,2,4,8,16,32,64,128,247,248,750\}</math>, <math>\sigma(A)=x \forall 1\leq x\leq 1500</math>. | |
<br/>Thus, <math>\{1,2,4,8,16,32,64,128,247,248,750\}</math> is a <math>11</math>-<math>1500</math> set. | <br/>Thus, <math>\{1,2,4,8,16,32,64,128,247,248,750\}</math> is a <math>11</math>-<math>1500</math> set. | ||
Line 42: | Line 42: | ||
<br/> | <br/> | ||
<br/> | <br/> | ||
− | Now, let's assume for contradiction that <math>\exists a_{10}\ | + | Now, let's assume for contradiction that <math>\exists a_{10}\leq 247</math> such that <math>{a_1, a_2, \dots, a_{11}}</math> is a <math>11</math>-<math>q</math> set where <math>q\geq 1500</math> |
− | <math> | + | <math>{a_1, a_2, \dots a_8}</math> is a <math>8</math>-<math>a</math> set where <math>a\leq 255</math> (lemma). |
− | <math>max{(a_9)}=a_{10}-1\ | + | <math>max{(a_9)}=a_{10}-1\leq 246</math> |
− | Let <math>\ | + | Let <math>{a_1, a_2, \dots, a_{10}}</math> be a <math>10</math>-<math>b</math> set where the first <math>8</math> elements are the same as the previous set. Then, <math>256+a_9+a_{10}</math> is not expressible as <math>\sigma(Y)</math>. Thus, <math>b\leq 255+a_9+a_{10}\leq 748</math>. |
− | In order to create a <math>11</math>-<math>d</math> set with <math>d>748</math> and the first <math>10</math> elements being the ones on the previous set, <math>a_{11}\ | + | In order to create a <math>11</math>-<math>d</math> set with <math>d>748</math> and the first <math>10</math> elements being the ones on the previous set, <math>a_{11}\leq 749</math> because we need to make <math>749</math> expressible as <math>\sigma(Y)</math>. Note that <math>b+1+a_{11}</math> is not expressible, thus <math>d<b+1+a_{11}\leq 1498</math>. |
<br/> | <br/> | ||
Done but not elegant... | Done but not elegant... | ||
− | == | + | == See Also == |
{{USAMO box|year=1992|num-b=2|num-a=4}} | {{USAMO box|year=1992|num-b=2|num-a=4}} | ||
− | + | {{MAA Notice}} | |
− | + | [[Category:Olympiad Combinatorics Problems]] | |
− | [[Category:Olympiad |
Latest revision as of 07:52, 19 July 2016
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)
Furthermore, 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
).
Furthermore, 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
.
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,
,
.
which implies that
,
.
Similarly ,
and
,
.
Thus, is a
-
set.
Now, let's assume for contradiction that such that
is a
-
set where
is a
-
set where
(lemma).
Let 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...
See Also
1992 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.