## Wednesday, April 5, 2006

### Partially Some! Topic: Algebra/Sequences & Series. Level: Olympiad.

Problem: Let $a_1, a_2, \ldots, a_n$ be reals such that $a_1+a_2+\cdots+a_n = 0$. Show that there exists $i \in \{1,2,\ldots,n\}$ such that $a_i$, $a_i+a_{i+1}$, $\ldots$, $a_i+a_{i+1}+\cdots+a_{i+n-1}$ are all nonnegative, where the indices are taken modulo $n$.

Solution: Let $j$ be the value of $m$ for which the partial sum $a_1+a_2+\cdots+a_m$ is minimum ($m = 1,2,\ldots,n$). We claim that $i = j+1$ satisfies the property that $a_i$, $a_i+a_{i+1}$, $\ldots$, $a_i+a_{i+1}+\cdots+a_{i+n-1}$ are all nonnegative.

Suppose $a_i+a_{i+1}+\cdots+a_{i+k} < 0$. Then the partial sum

$a_1+a_2+\cdots+a_{i+k} < a_1+a_2+\cdots+a_{i-1} = a_1+a_2+\cdots+a_j$.

If $i+k > n$,

$(a_1+a_2+\cdots+a_n)+a_{n+1}+a_{n+2}+\cdots+a_{i+k} = a_{n+1}+a_{n+2}+\cdots+a_{i+k}$.

Taking the indices modulo $n$, we have

$a_1+a_2+\cdots+a_{i+k-n}$,

which is also a partial sum. But we chose $j$ such that the partial sum was minimum, so we have a contradiction.

Hence none of the sums can be negative, as desired. QED.

--------------------

Comment: Playing around with numbers (and looking at graphs), it's not hard to conjecture the initial claim. Proving it rigorously came soon after by looking at partial sums.

--------------------

Practice Problem: For any finite set $A \subseteq \mathbb{R}$, define$f(A) = \max(A) - \min(A)$. Take $S = \{1,2,\,\cdots,n\}$. Find $\displaystyle \sum_{A \subseteq S} f(A)$.