APMO 00/5 solution

12th APMO 2000

Problem 5

Given a permutation s₀, s₂, ... , s_n of 0, 1, 2, .... , n, we may transform it if we can find i, j such that s_i = 0 and s_j = s_i-1 + 1. The new permutation is obtained by transposing s_i and s_j. For which n can we obtain (1, 2, ... , n, 0) by repeated transformations starting with (1, n, n-1, .. , 3, 2, 0)?

Solution

Experimentation shows that we can do it for n=1 (already there), n = 2 (already there), 3, 7, 15, but not for n = 4, 5, 6, 8, 9, 10, 11, 12, 13, 14. So we conjecture that it is possible just for n = 2^m - 1 and for n = 2.

Notice that there is at most one transformation possible. If n = 2m, then we find that after m-1 transformations we reach

1  n  0  n-2  n-1  n-4  n-3 ... 4  5  2  3

and we can go no further. So n even fails for n > 2.

If n = 15 we get successively:

 1  15  14  13  12  11  10   9   8   7   6   5   4   3   2   0   start
 1   0  14  15  12  13  10  11   8   9   6   7   4   5   2   3   after 7 moves
 1   2   3   0  12  13  14  15   8   9  10  11   4   5   6   7   after 8 more moves
 1   2   3   4   5   6   7   0   8   9  10  11  12  13  14  15   after 8 more moves
 1   2   3   4   5   6   7   8   9  10  11  12  13  14  15   0   after 8 more moves

This pattern is general. Suppose n = 2^m - 1. Let P₀ be the starting position and P_r be the position:

1   2   3 ... R-1   0,   n-R+1  n-R+2  n-R+3 ... n,   n-2R+1  n-2R+2 ... n-R, ... , R  R+1 ... 2R-1

Here R denotes 2^r and the commas highlight that, after the initial 1 2 ... R-1 0, we have increasing runs of R terms. If we start from P_r, then the 0 is transposed successively with R, 3R, 5R, ... , n-R+1, then with R+1, 3R+1, ... , n-R+2, and so on up to 2R-1, 4R-1, ... , n. But that gives P_r+1. It is also easy to check that P₀ leads to P₁ and that P_m is the required finishing position. Thus the case n = 2^m - 1 works.

Now suppose n is odd but not of the form 2^m - 1. Then we can write n = (2a + 1)2^b - 1 (just take 2^b as the highest power of 2 dividing n + 1). We can now define P₀, P₁, ... , P_b as before. As before we will reach P_b:

1 2 ¼ B-1 0, 2aB 2aB+1¼ (2a+1)B-1, (2a-1)B ¼ 2aB-1, ¼ , 3B, 3B+1, ¼ 4B-1, 2B, 2B+1, ¼ , 3B-1, B, B+1, ¼ , 2B-1

where B = 2^b - 1. But then the 0 is transposed successively with B, 3B, 5B, ... , (2a-1)B, which puts it immediately to the right of (2a+1)B-1 = n, so no further transformations are possible and n = (2a+1)2^b - 1 fails.

12th APMO 2000