Placing the integers $\{1,2,\ldots,n\}$ on a circle ( for $n>1$) in some special order

Solution 1:

I think I have got an answer : The arrangement is possible for any $n\ge 1$ .

Proof :

$\underline {case 1}$ , $n$ is even :

$n$ is even , so pair the numbers $1,2,...,n$ into $n/2$ pairs with the two numbers in each pair adding to $n+1$ i.e. the pairing is like $\{1,n\} ; \{2,n-1\} ; ...;\{\dfrac n2 , \dfrac n2+1\}$ . We claim that any circular arrangement of the numbers $1,2,...,n$ that keeps the numbers in each pair adjacent to one another gives all possible sum values from $1 $ to $\dfrac {n(n+1)}2$ . To see this , consider any $s$ as $1\le s \le \dfrac {n(n+1)}2$ , by division algorithm , there are integers $q,r$ such that $s=q(n+1)+r$ , where $0\le r\le n$ and $0 \le q \le n/2$ . If $r=0$ then we choose any $q$ consecutive pairs , as numbers in each pair are adjacent , this gives a connected subset with sum ( since each pair has sum $n+1$) $q(n+1)=q(n+1)+r(=0)=s$ ; if $r>0$ ( and so that $q < n/2)$ , we choose the connected subset to be beginning with $r$ and then $q$ consecutive pairs clockwise or anticlock wise as appropriate , obtaining a sum equal to $r+q(n+1)=s$

[Note :In $s=(n+1)q+r$ , the inequality $0\le r \le n$ comes from division algorithm but the bounds $0\le q \le n/2$ does not come directly from division algorithm ; it is due to as follows : $q(n+1)=s-r\le s \le \dfrac {n(n+1)}2$ so $q \le n/2$ , and $q(n+1)=s-r\ge1-r\ge1-n=-(n-1)>-(n+1)$ , so that $q>-1$ , then since $q$ is an integer , we get $q \ge 0$ ]

$\underline {case 2}$ , $n$ is odd :

$n$ is odd ,then we form $\dfrac {n+1}2$ pairs each with sum $n$ , thinking of the singleton $n$ as a degenerate pair ; i.e. $\{1,n-1\};\{2,n-2\};...;\{\dfrac {n-1}2 , \dfrac {n+1}2\};\{n\}$ are the required pairs . Here also , any arrangement that keeps the numbers in each pair adjacent to one another gives all possible sum , the justification being same as that of the previous one .

Solution 2:

Note that this is not meant as an answer to the OP's question, but the space in the comment fields is too limited, so I put my comment here.

Using brute (computer) force, I managed to find solutions for all $n\leq 26$, and it is quite likely that solutions for larger $n$ can be found. I still can't make up my mind, though, whether or not I believe that there is an integer $N$ for which the problem has no solutions:

I modified my program to count the number of possible solutions out of all permutations of the integers $1,\ldots,n$ on the circle (not counting rotations and reflections) and looked at the ratios of these numbers:

2: 1 solution(s) found (out of 1 possible). Ratio is 1.0
3: 1 solution(s) found (out of 1 possible). Ratio is 1.0
4: 2 solution(s) found (out of 3 possible). Ratio is 0.6666666666666666
5: 10 solution(s) found (out of 12 possible). Ratio is 0.8333333333333334
6: 41 solution(s) found (out of 60 possible). Ratio is 0.6833333333333333
7: 126 solution(s) found (out of 360 possible). Ratio is 0.35
8: 537 solution(s) found (out of 2520 possible). Ratio is 0.2130952380952381
9: 3956 solution(s) found (out of 20160 possible). Ratio is 0.19623015873015873
10: 19776 solution(s) found (out of 181440 possible). Ratio is 0.10899470899470899
11: 76340 solution(s) found (out of 1814400 possible). Ratio is 0.04207451499118166
12: 388047 solution(s) found (out of 19958400 possible). Ratio is 0.019442791005291005
13: 2775155 solution(s) found (out of 239500800 possible). Ratio is 0.011587247307733419
14: 15013424 solution(s) found (out of 3113510400 possible). Ratio is 0.004822024683135794

The program is currently busy to get the figures for $n=15$. I'm sure it can be somewhat optimized, but I don't expect that many additional values can be computed in acceptable time, so there probably won't be much more insight than what's available already:

It is clear to see that while the absolute numbers of admissible permutations grow with $n$, the ratios with respect to the total numbers of permutations decrease, but they do so quite irregularly, note that the ratios for $n=8$ and $n=9$ are quite close whereas in other places there is a drop by more than 50%, so it is not only size that matters, but possibly some number theoretic constellations.

So, this limited evidence supports both possible propositions: The growing number of solutions suggests that there is a solution for every integer, and the decreasing ratios as well as the irregularity in the numbers of solutions could be a sign that eventually there might be a number $N$ for which no solution exists.

Can anyone provide some additional thoughts on the problem? I think that it is quite a gem, but I don't really have an idea how to tackle it.