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

No comments:

Post a Comment