# Minimization of the maximal adjacent integer sums on a circle

Arrange $\{1,2,\cdots,n\}$ on a circle. What are the arrangements that minimize the maximal sum of all adjacent $k$ integers? For specific and low $n$'s it has been pointed out in math.stackexchange.com this problem can be solved with the binary linear programming. I would like to know if there are general solution for arbitrary $(n,k)$. A random algorithm that gives a probabilistic bound would be great, too.

• An easy lower bound is $\lceil k(n+1)/2\rceil$ (as, for any arrangement, $k(n+1)/2$ is the average, over all sets of $k$ adjacent integers, of their sum). An upper bound, for even $k$, appears to be $k(n+2)/2$, obtained by e.g. $1, n, 2, n-1, 3, n-2, \ldots, n/2-1, n/2$ (for even $n$). For $k$ even this upper bound exceeds the lower bound by $k/2$. For the special case of $k=2$ the upper bound is tight (as $n$ must be next to a number 2 or larger.) How precise do you need your bounds to be? – Neal Young Jun 23 '18 at 21:09
• Yes, I should have mentioned these easy bounds. I have also tried other simple strategies. I would like to have tighter bounds which presumably require more sophisticated strategies or techniques. It is hard to say exactly how tight the bound I would like except the tighter the better. How about I ask if $\lfloor k(n+1)/2\rfloor+c$ for some constant is an upper bound? – Hans Jun 23 '18 at 23:52
• For how large a value of $n,k$ do you want to be able to solve this? – D.W. Jun 24 '18 at 4:54
• @D.W.: The best is for arbitrary $(n,k)$ but if you have an asymptotic result or tight bounds for large $(n,k)$ would be great too. If there is a general pattern or property the optimal arrangement would take on, that would be nice as well. In general, any interesting results are welcome. – Hans Jun 24 '18 at 7:21
• When $n=2k$ and $k$ is odd the answer is $\lceil k(n+1)/2\rceil = k(n+1)/2+1/2$. The upper bound can be obtained by any arrangement where each odd position $i$ on the circle has some odd number $j$, and its antipodal position $(i+k) \bmod n$ has even number $j+1$. When $n=ka$ and $a$ and $k$ are relatively prime, I think a generalization of this construction gives an upper bound of about $k(n+1)/2 + k'(a - k')/2$ where $k' = k \bmod a$. The additive "error" term $k'(a-k')/2$ is between $(a-1)/2$ and $a^2/8$, so is constant when $a$ is constant. – Neal Young Jun 24 '18 at 17:21