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 4 of 5: Prove the inductive transition

P_r \to P_{r+1}

to establish

n = 2^k - 1

Previous step Next step

In plain words

Think of $P_r \to P_{r+1}$ as an in-place merge sort: $R$ leftward sweeps peel elements one by one off every second block of size $R$ and weld them onto the adjacent blocks to form blocks of size $2R$ .

P_r \xrightarrow{u = 0, 1, \ldots, R-1} P_{r+1} \implies P_k = [1 : 2^k-1], (0) \text{ for } n = 2^k - 1

Detailed analysis

Suppose $2R \mid N$ and we are at $P_r$ . For each $u = 0, 1, \ldots, R-1$ in turn, $0$ sits right after $R + u - 1$ and performs a leftward pass swapping successively with $R+u, 3R+u, \ldots, N-R+u$ , which are the leading elements of the odd-numbered blocks after $(0)$ . Each pass appends $R+u$ to the initial block $[1 : R+u-1]$ , transfers one element from each odd-numbered block to the end of the preceding even-numbered block, and shrinks the odd-numbered blocks by $1$ . After all $R$ passes ( $u = 0, \ldots, R-1$ ), the odd-numbered blocks vanish and the even-numbered blocks double to size $2R$ , yielding $P_{r+1}$ . When $n = 2^k - 1$ , we have $N = 2^k$ , so induction reaches $P_k = [1 : n], (0) = (1, 2, \ldots, n, 0)$ .