1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Neal Young Jun 23 '18 at 21:09
  • $\begingroup$ 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? $\endgroup$ – Hans Jun 23 '18 at 23:52
  • $\begingroup$ For how large a value of $n,k$ do you want to be able to solve this? $\endgroup$ – D.W. Jun 24 '18 at 4:54
  • $\begingroup$ @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. $\endgroup$ – Hans Jun 24 '18 at 7:21
  • $\begingroup$ 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. $\endgroup$ – Neal Young Jun 24 '18 at 17:21

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.