1992 USAMO Problems/Problem 3

Revision as of 00:51, 13 April 2012 by Danielguo94 (talk | contribs) (Solution)

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)


Futhermore, 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$).


Futhermore, 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 $\nexist \sigma(Y)=p+1$ (Error compiling LaTeX. Unknown error_msg).


Lemma) If $Z$ is a $n$-$p$ set, $p\le 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\le p+1+a_{n+1}\le2^{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, $\exist Y\subseteq\{1,2,4,8,16,32,64,128\}$ (Error compiling LaTeX. Unknown error_msg), $\sigma(Y)=x \forall 1\le x\le255$.

$248\le\sigma(y)+a_9\le502$ which implies that $\exist A\subseteq\{1,2,4,8,16,32,64,128,247\}$ (Error compiling LaTeX. Unknown error_msg), $\sigma(A)=x \forall 1\le x\le502$.

Simlarly $\exist B\subseteq\{1,2,4,8,16,32,64,128,247,248\}$ (Error compiling LaTeX. Unknown error_msg), $\sigma(A)=x \forall 1\le x\le750$ and $\exist C\subseteq\{1,2,4,8,16,32,64,128,247,248,750\}$ (Error compiling LaTeX. Unknown error_msg), $\sigma(A)=x \forall 1\le x\le1500$.


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}\le 247$ such that $\left {a_i}\right|_{1\le i\le11}$ (Error compiling LaTeX. Unknown error_msg) is a $11$-$q$ set where $q\ge1500$

$\left {a_i}\right|_{1\le i\le8}$ (Error compiling LaTeX. Unknown error_msg) is a $8$-$a$ set where $a\le255$ (lemma).

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

Let $\left {a_i}\right|_{1\le i\le10}$ (Error compiling LaTeX. Unknown error_msg) 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\le255+a_9+a_{10}\le748$.

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}\le749$ 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}\le1498$.


Done but not elegant...

Resources

1992 USAMO (ProblemsResources)
Preceded by
Problem 2
Followed by
Problem 4
1 2 3 4 5
All USAMO Problems and Solutions