Arrange $\{1,2,\cdots,n\}$ on a circle. What are the arrangements that minimize the maximal sum of all adjacent $k$ integers? Some nontrivial examples of $(n,k)$ are welcome. A random algorithm that gives a probabilistic bound would be great.

  • $\begingroup$ It's not quite clear what you're asking. Perhaps a graphic illustrating how you're arranging the integers? How are you defining "maximal sum of all adjacent $k$ integers"? $\endgroup$ – Adrian Keister Jun 20 '18 at 19:23
  • $\begingroup$ @AdrianKeister: Given a circular arrangement of those $n$ natural numbers, consider the set $K$ of $k$ adjacent natural numbers on the circle. Take the set $S$ of the sums of those elements of $k$ adjacent natural numbers on the circle. The maximum $M$ of the element of $S$ is then a function of the circular arrangement. Now find the minimal $M$ amongst all the circular arrangements. Is this clear? I can certainly write the question in the formal language. But I thought it was clearer this way. Let me know what you think of it after my explanation. $\endgroup$ – Hans Jun 20 '18 at 19:52
  • 1
    $\begingroup$ You could formulate it as a mixed integer linear optimization problem to get some examples of optimal arrangements. $\endgroup$ – LinAlg Jun 21 '18 at 1:49
  • $\begingroup$ @LinAlg: Good idea. I need $n^2$ binary variables with associated $2n$ inequalities to express the distinctiveness of the $n$ variables to formulate the problem in the mixed integer linear programming, don't I? $\endgroup$ – Hans Jun 21 '18 at 3:44
  • $\begingroup$ Yes. Minimizing the maximum can be phrased with purely linear constraints. $\endgroup$ – LinAlg Jun 21 '18 at 11:29

we don't want the two largest numbers in the set: which is n and n-1 to be adjacent to each other: You can quickly figure out the pattern that the lower bound of the maximum adjacent sum is n+2:

enter image description here

The general pattern is to start with n - the greatest number - on the very top position and make sure that n-1 isn't beside n, and then if you can n-2 isn't beside either n or n-1 and n-3 isn't beside any of those and so on. I placed them exactly 2 spots away in the clockwise direction (although you could use the Counter-Clockwise convention instead).

  • $\begingroup$ No, it is not so simple. $\endgroup$ – Hans Jun 21 '18 at 3:08
  • $\begingroup$ @Hans Wait then what's wrong with my diagram? $\endgroup$ – ray lin Jun 21 '18 at 3:10
  • $\begingroup$ Your answer is very sloppy. You do not even specify what $k$ you are using. Apparently you set $k=2$. There is no proof 2even some kind of plausibility justification. $\endgroup$ – Hans Jun 21 '18 at 4:53
  • $\begingroup$ @ Hans I have a question, if my diagram is k=2 how would k = 3 work? Would I select 2 of the numbers to the CW position and 1 on the CCW position or something else? $\endgroup$ – ray lin Jun 21 '18 at 16:11
  • $\begingroup$ $k$ means the sum is over $k$ adjacent/consecutive natural numbers. $\endgroup$ – Hans Jun 21 '18 at 17:45

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.