11
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ What do you mean by second theorem and two moves? I couldnt understand what you meant. $\endgroup$ – Oray Feb 20 '16 at 17:07
  • $\begingroup$ Trivially, I can improve the theorems by saying "at most 51 moves" and "at least 3 moves", so is the real puzzle to improve the theorems as much as possible by finding the solution that uses the minimal number of moves? $\endgroup$ – Ninety-Three Feb 20 '16 at 17:17
  • 2
    $\begingroup$ do you have to put in between numbers in this game or can I put cards at the end or the beginning? $\endgroup$ – Oray Feb 20 '16 at 17:18
  • $\begingroup$ @Ninety-Three You have to find some $x$ that can be put into both theorems: so you could say ("at most 51" and "at least 51") or ("at most 3" and "at least 3"), but not ("at most 51" and "at least 3"). $\endgroup$ – 2012rcampion Feb 20 '16 at 17:18
  • 2
    $\begingroup$ Interesting. The answer appears to be (obviously) 51, but given the history of this series I doubt that I'm right. $\endgroup$ – frodoskywalker Feb 20 '16 at 20:01
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your third spoiler block is remarkably similar to one of the proofs in the paper which gives the full result: math.chalmers.se/~wastlund/Sorting.pdf $\endgroup$ – Peter Taylor Feb 21 '16 at 17:50
  • $\begingroup$ @PeterTaylor I agree there is a remarkable similarity, but I daresay I was close to constructing this argument myself. It's not that deep (but it is beautiful). $\endgroup$ – Oliphaunt - reinstate Monica Feb 21 '16 at 21:31
  • $\begingroup$ @PeterTaylor Does that mean this q is solved? $\endgroup$ – ghosts_in_the_code Feb 22 '16 at 6:14
  • $\begingroup$ @ghosts_in_the_code, yes. Although I'm not convinced that it's on the right site. It's definitely a maths question, but IMO not a puzzle. $\endgroup$ – Peter Taylor Feb 22 '16 at 7:02
  • $\begingroup$ @PeterTaylor But you could post the answer anyways. $\endgroup$ – ghosts_in_the_code Feb 22 '16 at 7:03
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.