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 5 of 5: Rule out odd

n

not of the form

2^k - 1

and state the final answer

Previous step Next step

In plain words

Once the block size reaches the highest power of $2$ dividing $n + 1$ , there are an even number $2b$ of blocks left after $0$ , which mimics the even- $n$ trap and lands $0$ right behind $n$ .

n + 1 = 2^a(2b + 1) \ (a, b \ge 1) \implies P_a \longrightarrow ([1 : 2^a-1], \ldots, [N-2^a : N-1], 0, \ldots)

Detailed analysis

Finally, suppose $n$ is odd but not of the form $2^k - 1$ , so $N = n + 1 = 2^a(2b + 1)$ with integers $a \ge 1$ and $b \ge 1$ . Since $2^a \mid N$ , the same transitions lead from $P_0$ to $P_a$ , where $(0)$ is followed by $2b$ blocks of size $2^a$ : $[N-2^a : N-1], [N-2 \cdot 2^a : N-2^a-1], \ldots, [2^a : 2 \cdot 2^a - 1]$ . In the very next pass, $0$ swaps successively with $2^a, 3 \cdot 2^a, \ldots, (2b-1)2^a = N - 2 \cdot 2^a$ . Because $N - 2 \cdot 2^a$ is the first element of the second block $[N - 2 \cdot 2^a : N - 2^a - 1]$ , this swap places $0$ immediately after the last element $N - 1 = n$ of the first block $[N - 2^a : N - 1]$ , where the process halts incomplete. Hence the permutation is regular if and only if $n = 2$ or $n = 2^k - 1$ for a positive integer $k$ .