1
$\begingroup$

Given a sequence $(a_i)_1^n$ of real numbers that sum to $0$. There are $n$ circular permutations.

$\begin{array}{}\sigma_1 = &(a_1 &a_2 &\cdots &a_{n-1} &a_n)\\ \sigma_2 = &(a_2 &a_3 & \cdots &a_n &a_1)\\\sigma_3 = &(a_3& a_4& \cdots &a_1 &a_2)\\\vdots&\vdots\\\sigma_n = &(a_n& a_1& \cdots &a_{n-2} &a_{n-1})\end{array}$

Define $s_i(k)$ to be the sum of the first $k$ terms of permutation $\sigma_i$. Obviously, $s_i(n) = 0$.

Question: Does there always exist at least one permutation $\sigma_{p}$ such that the sequence $s_p(1), s_p(2), \cdots s_p(n-1)$ is non-negative?

Example 1: $(-10, 7, -8, 11)$

We find that there exists $\sigma_p = \sigma_4$ that gives a non-negative sequence of partial sums.

$\begin{array}{rrrrr|rrrr}\text{Index}&1&2&3&4&s(1)&s(2)&s(3)&s_(4)\\\hline\\\sigma_1:&-10&7&-8&11&-10&-3&-11&0\\\sigma_2:&7&-8&11&-10&7&-1&10&0\\\sigma_3:&-8&11&-10&7&-8&3&-7&0\\\sigma_{\color{green}{4}}:&11&-10&7&-8&\color{green}{11}&\color{green}{1}&\color{green}{8}&0\end{array}$

Example 2: $(1, 1, 1, 1, 8, 11, -29, 3, -7, 2, 1, 4, 4, -1)$

Here $\sigma_p = \sigma_{10} = (2, 1, 4, 4, -1, 1,1,1,1, 8, 11, -29, 3, -7)$ meets the requirement.

I feel that the property is true in general, but have no idea how to prove it.

Note: This question came to my mind while trying to understand the essence of this problem.

UPDATE: Here's an expansion of Daniel Fischer's answer.

Let the minimum $s_1(m) = -A \text{ for some } A \in \mathbb{R_{\ge 0}}$.

(1) Then the trailing terms $a_{m+1}, a_{m+2}, \cdots ,a_n$ contribute non-negative partial sums $a_{m+1}, a_{m+1} + a_{m+2}, \cdots$

Assume for some $1\le q \le n-m$, a negative partial sum $a_{m+1} + a_{m+2} + \cdots + a_{m+q}$. Then $s_1(m+q) = s_1(m) + a_{m+1} + a_{m+2} + \cdots + a_{m+q} < s_1(m)$ contra minimum $s_1(m)$.

Note that $a_{m+1} + a_{m+2} + \cdots + a_{n} = 0 - s_1(m) = A$

(2) For $1\le m' \le m$, we have by definition $s_1(m') \ge s_1(m)$.

$\begin{eqnarray}\implies a_{m+1} + a_{m+2} + \cdots + a_{n} + a_1 + a_2 + \cdots + a_{m'} &= &A + s_1(m')\\&\ge &A + s_1(m)\\&=&A -A\\&=& 0\end{eqnarray}$

Thus, from (1) and (2), we get the answer that $\sigma_{m+1}$ satisfies the required property.

$\endgroup$
2
$\begingroup$

Consider the finite sequence of partial sums $\bigl(s_1(k)\bigr)_{1 \leqslant k \leqslant n}$. There is at least one $m$ with

$$s_1(m) = \min \left\{ s_1(k) : 1 \leqslant k \leqslant n\right\}.$$

Then the cyclic permutation $\sigma_{m+1}$ (with the identification $\sigma_{n+1} = \sigma_1$ if $m = n$) has the desired property.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice! Took me a while to understand, but I now see why this works. I've updated the question to include some explanation of your answer. Thank you :) $\endgroup$ – Anant Jun 8 '14 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.