Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question is motivated by the following two questions and is a slightly generalized version of them.

Some three consecutive numbers sum to at least $32$

Integers $1, 2, \ldots, 10$ are circularly arranged in an arbitrary order.

Consider the first $n$ positive integers distributed along a circle in an arbitrary order. There are a total of $(n-1)!$ arrangements. Pick an arrangement $P_m$, where $m \in \{1,2,\ldots,(n-1)!\}$

The arrangement $P_m$ is of the form $a_{m,1},a_{m,2},\ldots,a_{m,n}$ around the circle where $a_{m,j} \in \{1,2,\ldots,n\}$ and $a_{m,i} \neq a_{m,j}$ whenever $i \neq j$.

Define a $k$-sum as the sum of $k$ consecutive numbers in an arrangement $P_m$. For instance, $$a_{m,1} + a_{m,2} + \cdots +a_{m,k},$$ $$a_{m,n-1} + a_{m,n} + a_{m,1} + a_{m,2} + \cdots + a_{m,k-2}$$ are examples of $k$-sums. Clearly for any arrangement $P_m$, there are $n$ such $k$-sums.

Now look at the maximum of these $k$-sums in the arrangement $P_m$, i.e. $$s_{m,k} = \max \{ (a_{m,1} + a_{m,2} + \cdots + a_{m,k}),(a_{m,2} + a_{m,3} + \cdots + a_{m,k+1}), \cdots, (a_{m,n} + a_{m,1} + \cdots + a_{m,k-1})\}$$

The question is what is the optimal lower bound of this maximum sum? i.e. What is $\displaystyle \min_{m} s_{m,k}$?

In Integers $1, 2, \ldots, 10$ are circularly arranged in an arbitrary order. it is shown that for $n=10$ and $k=3$, the optimal lower bound is $18$ and in Some three consecutive numbers sum to at least $32$, it is shown that the optimal lower bound for $n=20$ and $k=3$ is $\geq 33$.

Clearly, for $k=1$, $\displaystyle \min_{m} s_{m,1} = n$.

For $k=2$, $\displaystyle \min_{m} s_{m,2} = n+2$.

In general, a trivial lower bound is obtained by adding up all the $n$, '$k$' sums to get that $$n \times \min_{m} s_{m,k} \geq k \frac{n(n+1)}{2}$$ i.e. $\displaystyle \min_{m} s_{m,k} \geq \left \lceil k \frac{(n+1)}{2} \right \rceil$.

Clearly, this is not the optimal bound as seen from the results for $k=1$ and $k=2$ and also from the two questions: Some three consecutive numbers sum to at least $32$, Integers $1, 2, \ldots, 10$ are circularly arranged in an arbitrary order..

So the question is: What is the optimal lower bound? (I am also interested in better lower bounds even if the bound is not the optimal one. Any reference to articles where this has been discussed is welcome.)

EDIT

Some googling landed me on this article ( http://imi.cas.sc.edu/IMI/reports/2001/reports/0116.pdf ) where they have considered the same problem and have constructed better upper bounds for $\displaystyle \min_{m} s_{m,k}$. They prove that in general $$\displaystyle \min_{m} s_{m,k} \leq \min \left( \left \lceil \frac{k(n+1)}{2} + k + 6 \right \rceil, \left \lceil \frac{k(n+1)}{2} + \frac{k}{2} + 9 \right \rceil \right).$$ Further they prove that if $(n,k) > 1$, then the optimal lower bound is $$\displaystyle \min_{m} s_{m,k}\leq \left \lceil \frac{k(n+1)}{2} + \frac{7}{2} \right \rceil,$$ which I think is remarkable that the factor $\frac{7}{2}$ is independent of $k$ and $n$.

However, I am wondering if the lower bound of $\displaystyle \min_{m} s_{m,k}$ can be tightened further and if an exact value of $\displaystyle \min_{m} s_{m,k}$ can be obtained.

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.