6
$\begingroup$

Here is a problem I found on Google Plus.

Given a sequence $1,2,....,n$ you are allowed to interchange any two consecutive subsequences in it. Find the least number of steps in which you can reach $n,n-1,.....,1$ using this transformation. Consecutive subsequences means the last element of the first subsequence is less than the first element of the second subsequence.

Examples: $12345 \to 34125 \to 32541 \to 54321$ So, $T(5)=3$. Some other example are: $T(15)=11, T(13)=9, T(10)=7$

It has been found that, the transformation can always be done in at most $n-1$ ways by starting with $1,2,\ldots,n-1,n\to n,1,2...,n-1$ and then using induction. Is there a simple formula or method for finding the smallest number of ways instead of brute force?

  • 0
    I don't think I understand the question, because it seems to me that for any $n$ you can do it in $\lfloor n/2 \rfloor$ by switching opposing pairs: $1234567 \rightarrow 7234561 \rightarrow 7634521 \rightarrow 7654321$. Perhaps by subsequence you mean subsequence of length greater than 1?2012-02-20

1 Answers 1

1

This might not be optimal, but here's a better bound.

Starting with $1,2,\ldots,n$ interchange $ 1,2,\ldots,a,b,\ldots,n \rightarrow b,\ldots,n,1,\ldots\,a $ then reverse each of $[b\ldots n]$ and $[1\ldots a]$ in the optimal way. If we can do each part in $T(k)\le rk-1$ for some $r<1$ then $ T(n) \le 1+T(n-a)+T(a) \le 1+r(n-a)-1+ra-1 = rn-1 $ Since $T(5)=(4/5)\times 5-1$ we can bound $T(5k)\le 4k-1$ for all $k\ge 1$, and since $T$ must be nondecreasing, $T(n)\le 4\lceil\frac{n}{5}\rceil-1$ for all $n>0$. (This can be made marginally better by solving directly for $T(6),T(7),T(8),T(9)$.)

Given a permutation call an ordered pair of consecutive entries $(a,b)$ upward if $a. Then if we transform a general sequence $x_1,x_2,\ldots,x_i,y_1,\ldots\,y_j,z_1,\ldots,z_k,w_1,\ldots,w_l$ by one interchange to $x_1,x_2,\ldots,x_i,z_1,\ldots,z_k,y_1,\ldots\,y_j,w_1,\ldots,w_l$ then the number of upward pairs can decrease by at most 2, only if two of $z_1, $y_1 and $w_1 are true (all three cannot be simultaneously true). Since the initial sequence $1,2,\ldots,n$ has $n-1$ upward pairs and the final sequence must have zero, $T(n)\ge \lceil \frac{n-1}{2}\rceil$.

So $\lceil \frac{n-1}{2}\rceil \le T(n) < 4\lceil\frac{n}{5}\rceil$ for all $n>0$.