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
    The last move in your example does not seem valid. You are interchanging $32$ and $54$, but $2$ and $5$ are not consecutive.2012-02-04
  • 0
    Sorry, edited. It was meant "less than" rather than consecutive.2012-02-04
  • 0
    @scombinatori - I deleted my answer because I misunderstood what you were asking. I'll think about it and maybe post a new answer if I get something useful.2012-02-04
  • 0
    @svenkatr, thank you.2012-02-04
  • 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

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