Professor Halfbrain and the 52 cards

Question

Professor Halfbrain has spent his entire weekend by analyzing stacks of $52$ cards that are numbered by $1,2,\ldots,52$. Halfbrain always started with a stack having the cards face-up and in increasing order. A feasible move consists in picking a contiguous group of cards somewhere in the stack, taking out this group from the stack, and putting it back into the stack at some place (without changing the order within the group, and without turning over cards).

Example: A typical move would be to start with $1,2,\ldots,52$, to take out the group $4,5,6,7,8,9$, and to put it back between $16$ and $17$, so that the new stack becomes $1,2,3,10,11,12,13,14,15,16,\underline{4,5,6,7,8,9},17,18,\ldots,52$.

The goal is to bring the cards in the stack from increasing order into decreasing order, and to do this by making as few moves as possible. Professor Halfbrain has proved two extremely deep theorems on such rearrangement of stacks.

Professor Halfbrain's first theorem: It is possible to bring the cards in the stack from increasing order into decreasing order by making at most $52$ moves.

Professor Halfbrain's second theorem: For bringing the cards in the stack from increasing order into decreasing order, one must make at least two moves.

This puzzle asks you to improve the two theorems of professor Halfbrain and to make them even deeper. Find an integer $x$, so that "$52$ moves" in the first theorem may be replaced by "$x$ moves", and so that "at least two moves" in the second theorem may be replaced by "at least $x$ moves" (again yielding true statements, of course).

Answer 1

This is not a solution, but it is a demonstration that the answer is not 51.

5 cards can be reversed in 3 steps as follows:

12345
34125 (move 34 to the left)
32541 (move 41 to the right)
54321 (move 54 to the left)

 

25 cards can be reversed in 18 steps by doing that on five groups of five cards, then doing the same thing to rearrange the groups. So 52 cards can be reversed by reversing the first 25 (18 steps), then the second 25 (18 steps), then swapping the last two cards (1 step), and reordering the three blocks (2 steps), for a total of at most 39 steps.'

---

The answer must be at least

26.

Say a pair of consecutive cards is good if the first card is greater than the second. A generic move (moving x...y) looks like this:

...ax...yb...cd... -> ...ab...cx...yd...

There are three places where new pairs are formed (ab,cx,yd) and three places where pairs are lost (ax,yb,cd). The total gain is the number of created good pairs minus the number of destroyed good pairs. For this gain to be greater than 2, all three created pairs must be good, and all of the destroyed pairs must not be good. This requires that a>b>y>d>c>x>a, which is impossible. Therefore each step can only increase the number of good pairs by at most 2.

When the deck is in order, there are no good pairs. When it is reversed, there are 51 good pairs. So it takes at least 26 steps to reverse the deck.

Answer 2

The optimal solution is:

27

First an example of the algorithm with 10 elements:

1:2:3:4:5:6:7:8:9:10
5:6:1:2:3:4:7:8:9:10
5:4:7:6:1:2:3:8:9:10
5:4:3:8:7:6:1:2:9:10
5:4:3:2:9:8:7:6:1:10
5:4:3:2:1:10:9:8:7:6
10:9:8:7:6:5:4:3:2:1
For six swaps

The algorithm used follows:

The list consists of an empty list L2 at the start and a full list L1 at the beginning: L2:L1.
1. Take the middle two elements of L1 and move to the middle of L2
2. Repeat 1 until L1 is empty or contains 1 element. (This will take a number of operations that is half of the total number of elements)
3 Move the first half of L2 to after L2
The list is no sorted with N/2 + 1 operations

I will also only amend to the other solutions proof to show that the total number of swaps must be at least:

27
We already know that it takes at least 26 operations to create the final list. 25.5 to be more precise. Each move can at most increase the number of good pairs with 2. There are in total 51 pairs.
To prove that it will take at least 27 operations I will need to prove that in at least two operations there will only be an increase in the number of good pairs by 1.
The first operation: ...ax...yb...cd... -> ...ab...cx...yd...
leads to a>b>y>d>c>x>a
since it is the first operation we know that a In the final operation, we know that a>b>c>x>y>d. ax and cd are already good pairs. The only thing that remains unproven now are the edge scenarios were we are moving from an edge or to an edge. But that I leave for someone else to prove.