## Brainteaser 1785: Back to front

**From The Sunday Times, 1st December 1996** [link]

Given a row of eleven playing cards:

[

J] [10] [9] [8] [7] [6] [5] [4] [3] [2] [1]I wish to reverse the order to give:

[

1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [J]To do this we are allowed at any stage to make a “move” of the following type:

remove any section of adjacent cards from the pack and move them elsewhere.For example, one possible move from the starting position would be to take:

[

9] [8] [7]and move it to the right to give:

[

J] [10] [6] [5] [9] [8] [7] [4] [3] [2] [1]What is the minimum number of moves required to reverse them?

This puzzle was included in the book *Brainteasers* (2002, edited by Victor Bryant). The puzzle text above is taken from the book and differs slightly from the original puzzle.

[teaser1785]

## Jim Randell 11:51 am

on27 February 2020 Permalink |(See also:

Puzzle #32).We can measure the “disorderedness” of a list by going through it and looking how each element compares to the next element. If it is less than the next element, then it is “ordered”. If it is greater than the next element, then it is “disordered”.

Looking at the initial list we have:

which gives the following pairs:

all of which are disordered, giving the initial list a score of 10.

The target list is:

which gives the following pairs:

all of which are ordered, give the target list a score of 0.

Suppose the list is:

And we move the

[b … c]section to betweeneandf.Then we end up with

In the process we lose the adjacent pairs

(a, b) (c, d) (e, f)and we gain the adjacent pairs(a, d) (e, b) (c, f).So the best improvement we could hope for is if the first three pairs are disordered, and the second three pairs are ordered, then we has reduced the disorderedness score by 3.

For this to happen we need:

and:

We can write all six inequalities as the following chain:

So it is not possible for all the inequalities to hold simultaneously. So the best we can hope for in a move is to reduce the disorderedness score by 2.

A similar argument holds if a block is moved to the left.

Furthermore, if we consider the first move, we know the values

a, b, c, d, e, fare in descending order. So the pairs(a, b), (c, d), (e, f)are disordered, and of the pairs(a, d) (e, b) (c, f)only(e, b)is ordered, so we can only reduce the disorderedness by 1 on the first move.Similarly, on the final move the list ends up correctly ordered, and a similar argument shows that we can only reduce the disorderedness by 1 on the final move.

So, for a sequence of length 11, we start with a disorderedness score of 10, and to reduce this to a disorderedness score of 0 will require

at least6 moves (the score being reduced by 1+2+2+2+2+1 = 10). In general reversing a sequence of lengthn > 2will requireat least 1 + [n / 2]moves (where[x]denotes the integer part ofx).But can we achieve a reversal in 6 moves?

I wrote a program to try.

The following program can be used to examine the behaviour of sequences up to length 9 in less than 7s (and length 10 takes 23 minutes). All of these were achievable with the expected minimum number of moves. Unfortunately we want to know about sequences of length 11 (which takes 93m).

However, in my experiments with smaller sequences, I found that the minimal sequence found always had as an initial move, removing the two leftmost elements, and then re-inserting them at position

(m – 1) // 2(wheremis the length of the original sequence).Using this as the first move reduces the run time for a length 10 sequence to 6s, and produces a solution of 6 moves for a length 11 sequence in just 29s.

Run:[ @repl.it ]Solution:The minimum number of moves required is 6.Here is one set of 6 moves that achieves the reversal:

(Adjacent pairs that are ordered are linked with a hyphen).

LikeLike

## Jim Randell 11:19 am

on1 March 2020 Permalink |John Crabtree has come up with the following procedure to reverse a sequence using a minimal number of moves.

The first move partitions the sequence into an ordered sequence (to the left) and a subsequence from which ordered pairs can be removed and inserted into the ordered sequence (to the right). The total number of moves required is

1 + [n / 2].Here is the procedure used to reverse a length 11 sequence in 6 moves:

And here is the procedure encapsulated in a Python program:

Run:[ @repl.it ]LikeLike