Let $n$ and $k$ be integers with $k\leq n-2$. The absolute value of the sum of elements of any $k$-element subset of $\{a_1,a_2,\cdots,a_n\}$ is less than or equal to 1. Show that: If $|a_1|\geq1$, then for any $2\leq i \leq n$, we have: $$|a_1|+|a_i|\leq2$$
Problem
Source: CWMI 2016
Tags: combinatorics, absolute value
25.08.2016 16:34
Suppose $a_1\ge 1$. Order $a_2\ge\ldots a_j>0\ge a_{j+1}\ge\ldots a_n$. If $k\le j$, then $\sum^k_{i=1}a_i>1$, contradiction. Hence $k>j$. Since $k\le n-2$, there are at least $2$ negative numbers. If only $a_1$ is positive, consider $a_1+\sum^{n}_{i=n-k+2}a_i\le 1$, and $\sum^n_{i=n-k+1}a_i\ge -1$, subtracting the second equation from the first we have $|a_1|+|a_n|\le 2$. Since $|a_n|\ge |a_i|$ for $2\le i\le n-1$, the result is true. If at least $2$ numbers are positive, consider $a_1+a_2+\sum^{n}_{i=n-k+3}a_i\le 1$, and $\sum^n_{i=n-k+1}a_i\ge -1$, we get $|a_1|+|a_2|+|a_{n-1}|+|a_n|\le 2$. Since $|a_2|\ge |a_i|$ for $3\le i\le j$, and $|a_n|\ge |a_i|$ for $j+1\le i\le n-1$, the result holds as well. Case is similar when $a_1\le -1$.
23.07.2019 04:49
buzzychaoz wrote: $a_1+\sum^{n}_{i=n-k+2}a_i\le 1$, and $\sum^n_{i=n-k+1}a_i\ge -1$, the first equation should be $a_1+\sum^{n-1}_{i=n-k+1}a_i\le 1$
23.04.2021 20:02
This solution is much the same as above, but every step is natural. Suppose $a_1\ge 1$ And suppose $a_1,a_2,……,a_t$ is positive, $a_(t+1),a_(t+2),……,a_n\le 0$ If there's $a_2$ such that $a_2\ge a_1\ge 1$ regard $a_1+a_2+……+a_k\ge 1$, there must be at least one negative number from $a_1$ to $a_k$. As $k\le n-2$, so we have at least 2 nagative from $a_k+1$ to $a_n$. Hence, $a_3+a_4+……+a_k+a_i+a_j\le 1$, Which is a contradiction. Therefore $a_1$ is the largest. Suppose $a_n\le a_(n-1)\le ……\le a_(t+1)\le 0 < a_t\le ……\le a_2\le a_1$ Now, the condition $\Leftrightarrow$ $$|a_1+a_2+……+a_k|\le 1$$and $$|a_n+a_(n-1)+……+a_(n-k+1)|\le 1$$We want $$|a_1|+|a_2|\le 2$$and $$|a_1|+|a_n|\le 2$$(1) if $n-k-1\ge t+1$: We have: $$1\ge |a_n+a_(n-1)+……+a_(n-k+1)|\ge|a_n+a_k+a_(k-1)+……+a_(t+1)|$$Hence, $$|a_n|\le 1-|a_k+a_(k-1)+……+a_(t+1)|$$Also,$$1\ge |a_1+a_2+……+a_k|\ge a_1 -|a_k+a_(k-1)+……+a_(t+1)|$$Hence, $$|a_1|\le 1+|a_k+a_(k-1)+……+a_(t+1)|$$Add them together, we have $$|a_1|+|a_n|\le 2$$Notice that $$|a_k+a_(k-1)+……+a_(t+1)|\le 1$$Hence $$|a_t+a_(t-1)+……+a_2|\le 2\rightarrow \|a_1|+|a_2|\le 2$$(2) if $n-k-1< t+1$: Suppose $$|a_n+a_n-1+……+a_k+1|=X$$$$|a_k+a_(k-1)+……+a_(t+1)|=Y$$$$|a_t+a_(t-1)+……+a_(n-k+1)|=Z$$$$|a_(n-k)+a_(n-k-1)+……+(a_2)|=W$$We have $$X+Y-Z\le 1$$$$a_1+W+Z-Y\le 1$$Add them together, we have:$$a_1+W+X\le 2$$Hence, $$|a_1|+|a_n|+|a_2|\le 2$$We are done!
23.04.2021 20:35
What is CWMI?
23.04.2021 20:56
gabrupro wrote: What is CWMI? China Western Mathematical Invitational