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