A bridge catalogue has a machine for dealing cards. It can take a randomly arranged deck and divide it into four piles in any way you choose, but the order of the cards in each pile will be in the same order as they were in the deck.

Example: Deck starts as {5H 4C 3S 4S 4H 2D 3D 5S 2S 2C 5D 2H 5C 3C 4D 3H} Sort by suits creates piles: {5H 4H 2H 3H} {4C 2C 5C 3C} {2D 3D 5D 4D} {3S 4S 5S 2S}

Suppose that we run a deck through the machine several times, each time taking the four piles and placing them on top of each other in a fixed order. How many runs does it take to sort a deck into complete rank order, from ace of clubs to king of spades?

I really like Oscar's conjecture for a minimum. Here is another shot from first principles that give a 3 time cut process, though I don't prove it is minimum either. :-)

If I can get each suit sorted in the deck, a 4-deck cut on suit will finish the problem.

First 4-Cut:
A,5,9,K
2,6,10
3,7,J
4,8,Q

Second 4-Cut:
A,2,3,4
5,6,7,8
9,10,J,Q
K

Notice that the first 4-Cut makes sure that the cards are numerically ordered in each pile of the second 4-Cut, and the second 4-Cut makes sure the whole deck is numerically ordered. As I said above, my third 4-Cut will be by suits, finishing the sort. 

Now why is this minimum? And what happens with machines that produce a different number of piles? Definitely CS-sorting theory kinda stuff!

Posted by owl on 2004-11-13 07:38:49