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 2 of 5: Rule out all even

n > 2

after the first leftward pass

Previous step Next step

In plain words

In the first pass, $0$ hops left by two steps at a time; when $n$ is even, those two-step hops land $0$ directly behind $a_1 = n$ , trapping it prematurely.

n > 2\text{ even}: (1, n, n-1, \ldots, 3, 2, 0) \longrightarrow (1, n, 0, n-2, n-1, \ldots, 2, 3)

Detailed analysis

Assume $n \ge 3$ . Starting from $(1, n, n-1, \ldots, 3, 2, 0)$ , $0$ is preceded by $2$ and swaps with $3$ to jump two positions left; it is then preceded by $4$ and swaps with $5$ , and so on, successively swapping with $3, 5, \ldots, n-1$ when $n > 2$ is even. Because $n - 1$ sits at index $2$ immediately after $a_1 = n$ , swapping $0$ with $n - 1$ places $0$ right after $n$ in $(1, n, 0, n-2, n-1, \ldots, 2, 3)$ . No further legal transposition is possible, and since $n > 2$ , this is not $(1, 2, \ldots, n, 0)$ .