Problem 2093

Solution 1.
First consider the case when $n$ is odd. It is easy to see that
$$S = \sum_{i=1}^{n} |x_i - x_{i+2}| = \sum_{i=1}^{n} |y_i - y_{i+1}|$$
for another circular arrangement $y_1, y_2, \dots, y_n$. So we can consider
$$S = \sum_{i=1}^{n} |x_i - x_{i+1}|$$
instead. Now, the numbers $1$ and $n$ must appear somewhere on the circle. Suppose that the numbers between $1$ and $n$ clockwise are $z_1, z_2, \dots, z_k$ and the numbers between $1$ and $n$ anticlockwise are $w_1, w_2, \dots, w_l$, where $k + l = n - 2$. Then
$$|n - z_k| + |z_k - z_{k-1}| + \dots + |z_1 - 1| \ge (n - z_k) + (z_k - z_{k-1}) + \dots + (z_1 - 1) = n - 1$$
and
$$|n - w_l| + |w_l - w_{l-1}| + \dots + |w_1 - 1| \ge (n - w_l) + (w_l - w_{l-1}) + \dots + (w_1 - 1) = n - 1.$$
Adding these two inequalities yields
$$S \ge 2n - 2$$
(for later in the proof, we note that equality occurs if and only if the sequences $z_1, z_2, \dots, z_k$ and $w_1, w_2, \dots, w_l$ are in increasing order). Thus we can never have $S = 2n - 4$ for odd values of $n$.

Next consider the case when $n$ is even. Let the set of numbers appearing in the odd-indexed positions be $\mathcal{A}$ and let the set of numbers appearing in the even-indexed positions be $\mathcal{B}$. Here $|\mathcal{A}| = |\mathcal{B}| = n/2$.
Denote by $m_1$ and $M_1$ the minimum and maximum of $\mathcal{A}$, and denote by $m_2$ and $M_2$ the minimum and maximum of $\mathcal{B}$. Then, using a similar argument to the case of odd $n$ above, but replacing the numbers $1$ and $n$ by $m_1$ and $M_1$, we have
$$\sum_{i=1}^{n/2} |a_{2i} - a_{2i+2}| \ge 2(M_1 - m_1)$$
and doing the same but this time for the numbers $m_2$ and $M_2$, we have
$$\sum_{i=1}^{n/2} |a_{2i+1} - a_{2i+3}| \ge 2(M_2 - m_2).$$
Adding these two inequalities yields
$$S \ge 2(M_1 + M_2) - 2(m_1 + m_2)$$
It is easy to see that $\{m_1, m_2\} = \{1, m\}$ for some $m \le \frac{n}{2} + 1$ and $\{M_1, M_2\} = \{M, n\}$ for some $M \ge \frac{n}{2}$. So
$$\begin{aligned} S &\ge 2(n + M) - 2(1 + m) = 2n - 2 + 2(M - m) \\ &\ge 2n - 2 + 2\left(\frac{n}{2} - \frac{n}{2} - 1\right) = 2n - 4 \end{aligned}$$
To obtain equality, without loss of generality the numbers in odd-indexed positions must be placed in increasing order from $1$ to $\frac{n}{2}$ (both clockwise and anticlockwise). We count the arrangements as follows. First we place $1$ and $\frac{n}{2}$ somewhere on a circle. Then, we choose any subset of $\{2, 3, \dots, \frac{n}{2} - 1\}$ to be the values placed in increasing order clockwise from $1$ to $\frac{n}{2}$. After this, there is only one way to place the remaining values from $1, 2, \dots, n/2$ in increasing order anticlockwise from $1$ to $\frac{n}{2}$. We now have a circular arrangement of the odd-indexed numbers on the circle. This can be done in $2^{\frac{n}{2}-2}$ ways. Second, we follow the same procedure for the even-indexed numbers on the circle (this can also be done in $2^{\frac{n}{2}-2}$ ways). Finally, the (odd) circular offset between the values $1$ and $n$ can be chosen in $\frac{n}{2}$ ways, giving a total of $2^{\frac{n}{2}-2} \cdot 2^{\frac{n}{2}-2} \cdot \frac{n}{2} = n2^{n-5}$ circular arrangements.

Thus the answer to the question is $0$ if $n$ is odd, and $n2^{n-5}$ if $n$ is even.

Solution 2.
For all integers $k > 0$, we let $x_{n+k} := x_k$. We define a new circular arrangement by setting $a_1 = x_1$, $a_2 = x_3$, and more generally, $a_k = x_{2k-1}$. If $n$ is odd, say $n = 2m-1$, we find that $a_m = x_n$, $a_{m+1} = x_2$, etc. and we obtain a new circular arrangement $a_1, a_2, \dots, a_n$ of the numbers $1, 2, \dots, n$. If $n$ is even, say $n = 2m$, we find $a_m = x_{n-1}$, $a_{m+1} = x_1$ and the circular arrangement $a_1, a_2, \dots, a_m$ (we may call it the a-cycle) contains only half of the numbers $1, 2, \dots, n$. We then define a second circular arrangement (the b-cycle) by $b_k = x_{2k}$ for $k = 1, 2, \dots, m$. The circular arrangement $b_1, b_2, \dots, b_m$ contains those numbers from $1, 2, \dots, n$ which are not in the a-cycle. With this new notation, we find that
$$\sum_{i=1}^{n} |x_i - x_{i+2}| = \sum_{i=1}^{n} |a_i - a_{i+1}| \quad \text{if } n \text{ is odd,} \quad (21)$$
$$\sum_{i=1}^{n} |x_i - x_{i+2}| = \sum_{i=1}^{m} |a_i - a_{i+1}| + \sum_{i=1}^{m} |b_i - b_{i+1}| \quad \text{if } n = 2m \text{ is even.} \quad (22)$$
To facilitate the counting required for the problem, we prove the following lemma.

Lemma. If $m \ge 2$ and $a_1, a_2, \dots, a_m$ is a circular arrangement of $m$ distinct positive integers, where we let $a_{m+i} = a_i$ for $i > 0$, then
$$S(a) := \sum_{i=1}^{m} |a_i - a_{i+1}| \geq 2m - 2$$
with equality only possible when $a_1, a_2, \dots, a_m$ consists of $m$ consecutive numbers (not necessarily in their natural order) and the largest two numbers are direct neighbours in the cycle.

Proof. We use induction on $m \ge 2$. If $m = 2$, we have
$$S(a) = \sum_{i=1}^{2} |a_i - a_{i+1}| = 2|a_1 - a_2| \ge 2$$
with equality only if $a_2 = a_1 \pm 1$. If $m > 2$, after 'rotating' the cycle we can assume that $a_m$ is the largest number in the cycle. Let the cycle $a'$ be obtained from the cycle $a$ by removing $a_m$, i.e. $a'_i = a_i$ for $i = 1, 2, \dots, m-1$ but $a'_m = a'_1$. We then have
$$S(a) - |a_{m-1} - a_m| - |a_m - a_1| = S(a') - |a_{m-1} - a_1|$$
which implies, because $a_m > a_{m-1}$ and $a_m > a_1$,
$$S(a) - S(a') = 2a_m - a_{m-1} - a_1 - |a_{m-1} - a_1| = \begin{cases} 2(a_m - a_{m-1}) & \text{if } a_{m-1} > a_1 \\ 2(a_m - a_1) & \text{if } a_{m-1} < a_1. \end{cases}$$
We have $a_m - a_1 \ge 1$ as well as $a_m - a_{m-1} \ge 1$, and by inductive hypothesis, $S(a') \ge 2m - 4$, hence $S(a) \ge 2m - 4 + 2 = 2m - 2$ with equality only if $S(a') = 2m - 4$ and either $a_1$ or $a_{m-1}$ is equal to $a_m - 1$. In particular, in case of equality, the cycle $a'$ consists of consecutive numbers and its largest number is $a_m - 1$. The lemma follows. $\square$

A direct consequence of the Lemma is that for odd $n$ we have
$$\sum_{i=1}^{n} |x_i - x_{i+2}| \ge 2n - 2 > 2n - 4$$
and so $f(n) = 0$ for odd $n$, where $f(n)$ is the number of circular arrangements that satisfy the conditions of the problem.

Let now $n = 2m$ be even. From the Lemma we now obtain $\sum_{i=1}^{n} |x_i - x_{i+2}| = S(a)+S(b) \ge 2m-2+2m-2 = 2n-4$. To achieve equality, both cycles, $a$ and $b$, need to consist of consecutive numbers. One of these two cycles contains the numbers $1, 2, \dots, m$, the other the numbers $m+1, m+2, \dots, 2m$.
The Lemma allows us to count the number of cycles $a$ that consist of the numbers $1, 2, \dots, m$ (or any other $m$ consecutive numbers) for which $S(a) = 2m-2$. Let $g(m)$ be this number. Then $g(2) = 1$ as there is only one cycle of length two. For $m \ge 2$, the lemma implies that after removing the number $m$ from $a$, we are left with a cycle $a'$ that consists of the numbers $1, 2, \dots, m-1$ and which satisfies $S(a') = 2m-4$. Moreover, there are exactly two cycles $a$ which lead to the same $a'$, namely the two that are obtained by fitting in $m$ immediately before or after $m-1$ in $a'$. Hence $g(m+1) = 2g(m)$ for $m \ge 2$ and it follows by induction that $g(m) = 2^{m-2}$.

To determine $f(n)$ for $n = 2m$ even, we may assume that $x_1 = a_1 = 1$ so that we don't have to deal with rotational symmetry any more. From the above it then follows that the a-cycle consists of $1, 2, \dots, m$ and the b-cycle of $m+1, m+2, \dots, 2m$. As seen above, there are $g(m) = 2^{m-2}$ possibilities for the a-cycle. There are the same number of possible b-cycles, but when we merge the two to the full cycle $x_1 = a_1, x_2 = b_1, x_3 = a_2, x_4 = b_2, \dots, x_{n-1} = a_m, x_n = b_m$, a rotated b-cycle gives a different result. Therefore, we need to multiply by $m$, which is the number of possibilities to choose which element of the b-cycle will become $x_2$. This gives
$$f(n) = m g(m)^2 = m 2^{2m-4} = n 2^{n-5} \quad \text{for even } n = 2m.$$
Thus the answer to the question is $0$ if $n$ is odd, and $n2^{n-5}$ if $n$ is even.