Transform a pile of cards in reverse order

Question

There are 52 cards on a table and numbered in order from 1 to 52 with number 1 on top. The following operation can be repeatedly done: split the pile into two piles without shuffling and take cards from the top of the two piles in any order and build one new pile from top to bottom.

Example for a deck with 10 cards: given pile 1,2,3,4,5,6,7,8,9,10 make piles 1,2,3,4 and 5,6,7,8,9,10 and build a new pile such as 5,6,1,7,8,9,2,3,4,10.

What is the minimum number of operations, which is needed to revert the original pile, i.e. from 1,2,3,...,50,51,52 to 52,51,50,...,3,2,1?

Answer 1

The optimal strategy takes

six steps.

Here's why this is necessary:

Consider the reverse problem - instead of each action being "split the deck in two and merge them together", actions are "deal each card into one of two piles [top-down], and then stack one pile on top of the other". This is an exact inverse operation of the given one - anything you can do one way, you can do the other.

So, if you can reverse the deck with n "merges", you can also reverse it with n of my "two-pile deals": just do the same thing, but backwards. So instead, I will show that you need six two-pile deals to reverse the deck's order:

Imagine marking a pair of cards - say, 3 and 7. Watch just those two cards as a strategy is performed. If you choose "left" for both, or "right" for both, their relative order will not change: 3 will stay on top of 7. But of course, in the reversal, 7 will be on top of 3. So there must be at least one deal that splits these two cards up. And naturally, this works for every pair - every pair of cards must be split by one deal.

Assign each card a "path signature" - write L on the top of the card if you choose the left pile for it, and R if you choose the right pile. (So one card's path signature in a 7-deal strategy might be "LLRRLRL".) By the condition above, if your strategy works, every card's path signature must be different. If you use only 5 deals, that's only 32 possible path signatures. But we have more than 32 cards, so there must be at least six deals.

And here's a way to do it:

Like in the proof of optimality, I will essentially do it "backwards": dealing the cards into two piles, rather than taking the cards from two piles.

For each card, write its number as six binary digits.
First, make a "0" pile and a "1" pile based off of the rightmost binary digit. Stack the 1s on top of the 0s.
Then, make a "0" pile and a "1" pile based off of the second-from-right binary digit. Stack the 1s on top of the 0s.
Then, make a "0" pile and a "1" pile based off of the third-from-right binary digit...
Continue until reaching the leftmost digit.

This will sort the cards correctly, highest at the top. (Consider any two cards, and compare their binary numbers: the first digit where they differ tells you which is bigger, and that corresponds to the last time their relative order could be modified. Since we made sure that in that step, we sorted them correctly, and afterwards, their relative order did not change, they must be in the correct order in the final deck.)

...Of course, to actually convert this into a solution to the problem as stated, you need to do this while moving backwards in time. (Or, if you don't have a time machine handy, write down the permutations after each step, and do your deck-merging to make those permutations.)

Fun fact:

This strategy is actually a thing called radix sort! (And I believe some variant of mergesort can be modified to work for the original problem more directly.)

Answer 2

@Deusovi was a few hours earlier, but perhaps this answer gives a simpler argument for the lower bound and a more practical description of an optimal strategy.

Let N (=52) be the number of cards and k (=6) the smallest integer such that $N \le 2^k$.

First, let us show that at least k operations are required:

Given a deck of cards in a given order P let $U(P)$ be the length of any longest increasing subsequence. Example: $P = (0,4,5,2,6,3,8,7)$; longest increasing subsequence $(0,4,5,6,8)$ therefore $U(P)=5$

In the initial state $P_0$ (cards sorted upwards) $U(P_0)=N$, in the target state $P_\infty$ (cards sorted downwards) $U(P_\infty)=1$.

Therefore, if we can show that applying the operation does not reduce $U$ by more than half we are done. But this is easy to see: Splitting the deck in two also splits any longest increasing sequence in two. Neither the splitting nor the subsequent merging will change the fact that both halves are increasing. The larger half can therefore be used to establish a lower bound for the new U.

Optimal algorithm:

Let $b_kb_{k-1}...b_2b_1$ the binary representation of card number x. At iteration t transform x to $x_t$ by the following method: Starting from $x_0=x$ to get $x_{t+1}$ from $x_t$
(1) remove the most significant bit
(2) flip it and
(3) reattach it as the new least significant bit.

The binary representation of $x_t$ is then: $b_{k-t}...b_1¸\overline{b}_k...\overline{b}_{k-t+1}$.

If we can apply the operation in such a way that after $t$ iterations the cards are ordered increasingly w.r.t. $x_t$ we are done because $x_k$ is just $x$ with all bits (zero padded to k digits if necessary) flipped.

Assuming that the cards are ordered w.r.t. $x_t$
(1) we can split the deck at where the most significant bit switches
(3) as by assumption the two piles are ordered we can merge them in order, first by all other bits and
(2) then, in reverse order of the former most significant bit
It is easily seen that this will leave the cards ordered according to $x_{t+1}$