Problem 5

Given a permutation

(a_0, a_1, \ldots, a_n)

of the sequence

0, 1, \ldots, n

. A transposition of

a_i

with

a_j

is called legal if

a_i = 0

for

i > 0

, and

a_{i-1} + 1 = a_j

. The permutation

(a_0, a_1, \ldots, a_n)

is called regular if after a number of legal transpositions it becomes

(1, 2, \ldots, n, 0)

. For which numbers

n

is the permutation

(1, n, n-1, \ldots, 3, 2, 0)

regular?

Step 3 of 5: Define the block configuration

P_r

and reach

P_1

for odd

n

Previous step Next step

In plain words

When $n$ is odd, the first leftward sweep jumps all the way to $a_1 = n$ , pairing every even number with the odd number above it into sorted blocks of length $2$ .

P_r = [1 : R-1], (0), [N-R : N-1], [N-2R : N-R-1], \ldots, [2R : 3R-1], [R : 2R-1] \quad (R = 2^r,\ N = n+1)

Detailed analysis

For odd $n \ge 3$ , set $N = n + 1$ and $R = 2^r$ , and write $[a : b] = (a, a+1, \ldots, b)$ for a contiguous ascending block. Let $P_0$ be the initial permutation and define $P_r$ as $[1 : R-1], (0), [N-R : N-1], [N-2R : N-R-1], \ldots, [2R : 3R-1], [R : 2R-1]$ whenever $2R \mid N$ . In the first pass from $P_0$ , since $n$ is odd, $0$ swaps successively with $3, 5, \ldots, n$ , landing at index $1$ right after $1$ and pairing the remaining entries into $[N-2 : N-1], [N-4 : N-3], \ldots, [2 : 3]$ , which is exactly $P_1$ .