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 "1992 USAMO Problems/Problem 3"

m (→‎Solution)
m (→‎Resources)
 
(3 intermediate revisions by 3 users not shown)
Line 10: Line 10:
  
 
<br/>
 
<br/>
−
Futhermore, 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>).
+
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/>
−
Futhermore, 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>\nexist \sigma(Y)=p+1</math>.
+
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\le 2^n-1</math>.
+
<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\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\leq p+1+a_{n+1} \leq 2^{n+1}-1</math>
  
 
<b>Lemma Proven</b>
 
<b>Lemma Proven</b>
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>\exist Y\subseteq\{1,2,4,8,16,32,64,128\}</math>, <math>\sigma(Y)=x \forall 1\le x\le255</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>\exist A\subseteq\{1,2,4,8,16,32,64,128,247\}</math>, <math>\sigma(A)=x \forall 1\le x\le502</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>.
  
−
Simlarly <math>\exist 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>\exist C\subseteq\{1,2,4,8,16,32,64,128,247,248,750\}</math>, <math>\sigma(A)=x \forall 1\le x\le1500</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}\le 247</math> such that <math>\left {a_i}\right|_{1\le i\le11}</math> is a <math>11</math>-<math>q</math> set where <math>q\ge1500</math>
+
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>\left {a_i}\right|_{1\le i\le8}</math> is a <math>8</math>-<math>a</math> set where <math>a\le255</math> (lemma).
+
<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\le246</math>
+
<math>max{(a_9)}=a_{10}-1\leq 246</math>
  
−
Let <math>\left {a_i}\right|_{1\le i\le10}</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\le255+a_9+a_{10}\le748</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}\le749</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}\le1498</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}\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...
  
−
== Resources ==
+
== 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]]

Latest revision as of 06:52, 19 July 2016

Problem

For a nonempty set $S$ of integers, let $\sigma(S)$ be the sum of the elements of $S$. Suppose that $A = \{a_1, a_2, \ldots, a_{11}\}$ is a set of positive integers with $a_1 < a_2 < \cdots < a_{11}$ and that, for each positive integer $n \le 1500$, there is a subset $S$ of $A$ for which $\sigma(S) = n$. What is the smallest possible value of $a_{10}$?

Solution

Let's a $n$-$p$ set be a set $Z$ such that $Z=\{a_1,a_2,\cdots,a_n\}$, where $\forall i<n$, $i\in \mathbb{Z}^+$, $a_i<a_{i+1}$, and for each $x\le p$, $x\in \mathbb{Z}^+$, $\exists Y\subseteq Z$, $\sigma(Y)=x$, $\nexists \sigma(Y)=p+1$.

(For Example $\{1,2\}$ is a $2$-$3$ set and $\{1,2,4,10\}$ is a $4$-$8$ set)


Furthermore, let call a $n$-$p$ set a $n$-$p$ good set if $a_n\le p$, and a $n$-$p$ bad set if $a_n\ge p+1$ (note that $\nexists \sigma(Y)=p+1$ for any $n$-$p$ set. Thus, we can ignore the case where $a_n=p+1$).


Furthermore, if you add any amount of elements to the end of a $n$-$p$ bad set to form another $n$-$p$ set (with a different $n$), it will stay as a $n$-$p$ bad set because $a_{n+x}>a_{n}>p+1$ for any positive integer $x$ and $\nexists \sigma(Y)=p+1$.


Lemma) If $Z$ is a $n$-$p$ set, $p\leq 2^n-1$.


For $n=1$, $p=0$ or $1$ because $a_1=1 \rightarrow p=1$ and $a_1\ne1\rightarrow p=0$.

Assume that the lemma is true for some $n$, then $2^n$ is not expressible with the $n$-$p$ set. Thus, when we add an element to the end to from a $n+1$-$r$ set, $a_{n+1}$ must be $\le p+1$ if we want $r>p$ because we need a way to express $p+1$. Since $p+1$ is not expressible by the first $n$ elements, $p+1+a_{n+1}$ is not expressible by these $n+1$ elements. Thus, the new set is a $n+1$-$r$ set, where $r\leq p+1+a_{n+1} \leq 2^{n+1}-1$

Lemma Proven


The answer to this question is $\max{(a_{10})}=248$.

The following set is a $11$-$1500$ set:

$\{1,2,4,8,16,32,64,128,247,248,750\}$

Note that the first 8 numbers are power of $2$ from $0$ to $7$, and realize that any $8$ or less digit binary number is basically sum of a combination of the first $8$ elements in the set. Thus, $\exists Y\subseteq\{1,2,4,8,16,32,64,128\}$, $\sigma(Y)=x \forall 1\le x\leq 255$.

$248\le\sigma(y)+a_9\le502$ which implies that $\exists A\subseteq\{1,2,4,8,16,32,64,128,247\}$, $\sigma(A)=x \forall 1\le x\leq 502$.

Similarly $\exists B\subseteq\{1,2,4,8,16,32,64,128,247,248\}$, $\sigma(A)=x \forall 1\le x\le750$ and $\exists C\subseteq\{1,2,4,8,16,32,64,128,247,248,750\}$, $\sigma(A)=x \forall 1\leq x\leq 1500$.


Thus, $\{1,2,4,8,16,32,64,128,247,248,750\}$ is a $11$-$1500$ set.



Now, let's assume for contradiction that $\exists a_{10}\leq 247$ such that ${a_1, a_2, \dots, a_{11}}$ is a $11$-$q$ set where $q\geq 1500$

${a_1, a_2, \dots a_8}$ is a $8$-$a$ set where $a\leq 255$ (lemma).

$max{(a_9)}=a_{10}-1\leq 246$

Let ${a_1, a_2, \dots, a_{10}}$ be a $10$-$b$ set where the first $8$ elements are the same as the previous set. Then, $256+a_9+a_{10}$ is not expressible as $\sigma(Y)$. Thus, $b\leq 255+a_9+a_{10}\leq 748$.

In order to create a $11$-$d$ set with $d>748$ and the first $10$ elements being the ones on the previous set, $a_{11}\leq 749$ because we need to make $749$ expressible as $\sigma(Y)$. Note that $b+1+a_{11}$ is not expressible, thus $d<b+1+a_{11}\leq 1498$.


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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1992_USAMO_Problems/Problem_3&oldid=79521"