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?

(In reply to re: A less pure conjecture by Federico Kereki)

Yep, it wouldn't be too surprising if any 3-cut solution could be mapped to Oskar's solution via the right kind of numbering, or is that not the case? I guess I could have let the Ace have it's own cut-deck in the second cut.

And sure enough, there is an hidden optimality theorem, though all of this being reserved only for CS people is beyond me :-)

Posted by owl on 2004-11-13 18:24:10