7
$\begingroup$

There are $n$ real numbers, $a_1,\dots,a_n$, arranged on a circle. Given a fixed integer $k<n$, let $S_i$ be the sum of the $k$ adjacent numbers starting at $a_i$ and counting clockwise, like this (illustrated for $k=3$):

enter image description here

The sum of all $n$ numbers is $0$. What is the largest possible number of strictly-positive $S_i$?

Here are some lower bounds:

  • If $k\leq n/2$, then at least $n-k$ sums can be positive, e.g. when $a_1 = \cdots = a_{n-1} = 1$ and $a_n = -(n-1)$. There are $n-k$ sums that do not contain $a_n$, and they are positive.
  • If $k\geq n/2$, then at least $k$ sums can be positive, e.g. when $a_1 = \cdots = a_{n-1} = -1$ and $a_n = +(n-1)$. There are $k$ sums that contain $a_n$, and they are positive.

And here are some upper bounds:

  • If $n$ is even and $k=n/2$, at most $n/2$ sums can be positive. This is because, if a certain sum $S_i$ is positive, then its complement sum $S_{i+k}$ must be negative (since $S_i+S_{i+k}=0$).
  • If $k=n/3$, then at most $2n/3$ sums can be positive, since if $S_i$ and $S_{i+k}$ are positive, then $S_{i+2k}=-(S_i+S_{i+k})$ must be negative.
  • Similarly, if $k=n/a$ for some integer $a$, then at most $(a-1)n/a$ sums can be positive.

What is the general answer as a function of $k$?

$\endgroup$
  • 2
    $\begingroup$ The result is invariant under $k\to n-k$, since we can flip the signs on any configuration. (If there are any zero sums, we can make them strictly negative first by perturbing the entries gently enough that it doesn't affect the strictly positive sums.) Then your bounds seem to suggest that the answer may be $\frac n2+\left|\frac n2-k\right|$. $\endgroup$ – joriki Jun 24 '16 at 8:30
  • $\begingroup$ If $n=qk+r$, then we can get $n-r$ positive sums; set $r$ consecutive values to be $x$, then of the remaining, set every $k-1$ values to $y$ and the $k$th value to be $z$; now $x,y,z$ can be chosen suitable, eg: $y=\dfrac{1}{k}$. $\endgroup$ – Aravind Jun 25 '16 at 5:19
2
$\begingroup$

This isn't a complete answer (no upper bounds), but some more general constructions and remarks that make it too long for a comment.

As joriki pointed out, we can assume $n \ge 2k$.

The first construction is due to Aravind (see the comment above). Suppose $n = qk + r$, $q \ge 2$ and $1 \le r \le k-1$ (if $r = 0$, then $k | n$, and then we know there can be $n - k$ positive sums, and this is best possible). Now for $1 \le i \le n$, set $ a_i = \begin{cases} k - 1 + \frac{r}{q} & \mbox{if } k | i, \\ -1 &\mbox{otherwise.}\end{cases}$ We then have $\sum_{i=1}^n a_i= 0$.

Any sum containing one of the $a_{jk}$ is positive, so the only negative sums are $S_{qk+1}, S_{qk+2}, ..., S_{qk+r}$. Thus there are $n-r$ positive sums. If $r = 1$, this is clearly optimal.

Note also that any placement of the $q$ positive terms, provided they are at least $k$ apart, works, since all $qk = n-r$ sums involving the positive terms will be positive.

When $r > \frac{k}{2}$, there is a construction that does better: it gives $n - k + r$ positive sums instead. If $r = k-1$, this is again best possible. For $1 \le i \le n-1$, set $a_i = \begin{cases} - \left(k-1- \frac{1}{2q} \right) &\mbox{if } k|i, \\ 1 &\mbox{otherwise.}\end{cases}$ Let $a_n = -\left(r - \frac12 \right)$. We again have $\sum_{i=1}^n a_i = 0$.

Any sum involving only one negative term is positive, hence the only negative sums have two negative terms. The only such sums have both $a_{qk}$ and $a_n$, and are $S_{n-k+1}, S_{n-k+2}, ..., S_{n-r}$ (recall that $qk = n-r$). Hence there are $k-r$ negative sums, and thus $n-k+r$ positive sums.

Finally, I'd like to point out that if the answer had indeed been $n-k$, this would have proven the Manickam-Miklos-Singhi conjecture. The MMS conjecture has been the focus of much recent research. It claims that if $n \ge 4k$, then for any collection of $n$ numbers summing to $0$, there are at least $\binom{n-1}{k-1}$ subsets of size $k$ with non-positive sum. This can be achieved, for example, by taking one number to be $-(n-1)$, and the others to be $1$. The difficulty is in proving that there cannot be fewer.

This is known to be true if $k | n$, or if $n \ge 10^{46} k$ (a result of Pokrovskiy (paper)). The condition $n \ge 4k$, or something similar, is necessary, since counterexamples are known for smaller $n$ (e.g. $n = 3k+1$).

Now suppose in this cyclic version, we could never have more than $n-k$ positive sums, so always had at least $k$ non-positive sums. If we take a random cyclic ordering of the $n$ elements, every cyclic $k$-set is a uniformly random $k$-set. Hence if at least $k$ have non-positive sum, that implies that at least a $\frac{k}{n}$-proportion of all $k$-sets, or $\binom{n-1}{k-1}$ $k$-sets, have non-positive sum, proving the conjecture.

Sadly, however, the above examples show that this cannot be used to prove the Manickam-Miklos-Singhi conjecture (at least not without additional work).

$\endgroup$
  • $\begingroup$ Wow. I did not know that this apparently simple question is related to an open conjecture! $\endgroup$ – Erel Segal-Halevi Jun 26 '16 at 14:43

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.