Let $a_1, a_2, ....., a_{2003}$ be sequence of reals number. Call $a_k$ $leading$ element, if at least one of expression $a_k; a_k+a_{k+1}; a_k+a_{k+1}+a_{k+2}; ....; a_k+a{k+1}+a_{k+2}+....+a_{2003}$ is positive. Prove, that if exist at least one $leading$ element, then sum of all $leading$'s elements is positive. Official solution here
Problem
Source:
Tags: algebra proposed, algebra, combinatorics proposed
22.01.2018 06:26
This is also doable, without induction. We will argue as follows. Start with the first leading term, say it is, $a_{n_1}$. If, $a_{n_1}>0$; add it to the sum, and, go on finding the second such term. If not, then, let, $\ell$ be the smallest index, for which, $$ a_{n_1}+a_{n_1+1}+\cdots+a_{n_1+\ell}>0. $$In this second case, $a_{n_1}$ is a leading term, and is zero. Clearly, $a_{n_1+\ell}>0$ (as, $\ell$ is the smallest such guy), hence, $a_{n_1+\ell}$ is also a leading term. Now, among the numbers, $$ a_{n_1+1},a_{n_1+2},\cdots,a_{n_1+\ell}, $$let, $I$ be the index of all, those are negative. We have, $$ \sum_{i\in \{n_1,n_1+1,\cdots,n_1+\ell\}\setminus I}a_i + \sum_{i\in I}a_i>0. $$Clearly, all the indices, contained in the first summation (namely, $i\in\{n_1,n_1+1,\cdots,n_1+\ell\}\setminus I$), $a_i$'s are leading terms. If, there is a subset $J\subseteq I$, such that, $a_j$ is a leading term, for every $j\in J$, we have, $$ \sum_{i\in \{n_1,n_1+1,\cdots,n_1+\ell\}\setminus I}a_i + \sum_{j\in J}a_j>\sum_{i\in \{n_1,n_1+1,\cdots,n_1+\ell\}\setminus I}a_i + \sum_{i\in I}a_i>0, $$hence, the sum of all leading terms, starting from, $a_{n_1}$, to, $a_{n_1+\ell}$ are positive. Now, search for the next leading term (namely, $a_k$, such that, $k>n_1+\ell$, with, $a_k$ leading); and notice that, we have a second block of leading terms, whose sum is positive. With this approach, we take each leading term, into account, at subsequent steps, based on the blocks, constructed above; and at each time, the sums in subblocks are all positive, proving that, the sum of all leading terms are positive, provided, a leading term exists.