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

For which integer $n>1$ can we place the integers $\{1,2,\ldots,n\}$ on a circle (say boundary of $S^1$ ) in some order such that for each $s \in \{1,2,\ldots,\dfrac {n(n+1)}{2}\}$ , there exist a connected subset of the circle on which the sum of the integers placed is exactly $s$?

Answer

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 .

Attribution
Source : Link , Question Author : Community , Answer Author : Community

Leave a Comment