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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.