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 1 of 5: Analyze the deterministic rule and check small values

n = 1, 2

Previous step Next step

In plain words

There are no choices to make: the game plays itself deterministically until $0$ lands right behind $n$ and halts.

a_i = 0 \ (i > 0) \implies a_j = a_{i-1} + 1; \qquad n = 1 \implies (1, 0), \quad n = 2 \implies (1, 2, 0)

Detailed analysis

Whenever $a_i = 0$ with $i > 0$ , a legal transposition looks at the entry $a_{i-1}$ immediately before $0$ and swaps $0$ with $a_j = a_{i-1} + 1$ . Thus at most one legal transposition is available at any moment, and none is possible if and only if $0$ is preceded by $n$ (or $i = 0$ , which never happens since $1$ stays at $a_0$ or $a_{i-1} \ge 1$ ). For $n = 1 = 2^1 - 1$ and $n = 2$ , the initial permutations $(1, 0)$ and $(1, 2, 0)$ are already equal to $(1, \ldots, n, 0)$ , so both $n = 1$ and $n = 2$ are regular.