Consider all finite sequences of positive real numbers each of whose terms is at most $3$ and the sum of whose terms is more than $100$. For each such sequence, let $S$ denote the sum of the subsequence whose sum is the closest to $100$, and define the defect of this sequence to be the value $|S-100|$. Find the maximum possible value of the defect.
Problem
Source: XIV Rioplatense Mathematical Olympiad (2005), Level 3
Tags: algebra unsolved, algebra
07.02.2012 13:57
$ a=a_{1}+....+a_{k-1} \leq 100 \leq a_{1}+....+a_{k-1}+a_{k}=b $. then the defect will be the minimum between $ 100-a $ and $ b-100 $. then will be $ \leq (b-a)/2 \leq 3/2 $. the maximum can be attained for example $ a_{1}=...=a_{32}=3,a_{33}=2.5,a_{34}=3 $.
07.02.2012 17:54
Sadly its defect would be 1 instead; the subsequence is all the 3. You have a misunderstanding of the definition of subsequence.
07.02.2012 20:46
do you want to say that a subsequence is any sequence of the form $ a_{i_{1}}, a_{i_{2}},.....,a_{i_{t}} $ where $ i_{1}<i_{2}<.....<i_{t} $?
07.02.2012 21:38
I'm confused. can somebody explain what is a subsequence in this case?
20.04.2017 20:26
The answer is $\boxed{\frac{100}{67}}$. To see that $\frac{100}{67}$ can indeed be attained, just take a constant sequence of $34$ terms all equal to $\frac{200}{67}$. The sum of any subsequence is of the form $\frac{200k}{67}$ for some integer $k$, and $\left|\frac{200k}{67}-100\right|=\frac{100}{67}|2k-67|\geq\frac{100}{67}$, with equality if $k=34$. Now it remains to prove that given any sequence $a_1, \ldots, a_n$ of real numbers such that $0\leq a_i\leq 3$ for each $i$ and $a_1+\cdots+a_n\geq 100$, we can find a subsequence whose sum $S$ satisfies $|S-100|\leq\frac{100}{67}$. WLOG assume $a_1\geq\cdots\geq a_n$ and denote by $m$ the smallest integer such that $$a_1+\cdots+a_m\geq 100\text{.}$$Clearly $a_1+\cdots+a_m\leq 3m$, hence $3m\geq 100$ and $m\geq 34$. Case 1: $a_m\leq\frac{200}{67}$. Let $S_1=a_1+\cdots+a_{m-1}$ and $S_2=a_1+\cdots+a_m$. By the minimality of $m$ we have $S_1<100$, and $S_2\geq 100$ by construction. Hence $$|S_1-100|+|S_2-100|=(100-(a_1+\cdots+a_{m-1}))+((a_1+\cdots+a_m)-100)=a_m\text{.}$$Since $a_m\leq\frac{200}{67}$ according to our hypothesis, it follows that one of the numbers $|S_1-100|$ and $|S_2-100|$ is at most $\frac{100}{67}$, and the result follows. Case 2: $a_m>\frac{200}{67}$. Then all numbers $a_1, \ldots, a_m$ are greater than $\frac{200}{67}$. Thus (recall that $m\geq 34$), $$a_1+\cdots+a_{34}>34\cdot\frac{200}{67}>100$$hence $m=34$. Now let $$S=a_1+\cdots+a_{33}\text{.}$$We have $S>33\cdot\frac{200}{67}=100-\frac{100}{67}$. Since $S<100$, it follows that $|S-100|<\frac{100}{67}$, and the result follows again.