In a paper entitled “Longest Increasing Subsequences: From Patience Sorting to the Baik-Deift-Johansson Theorem”, David Aldous and Persi Diaconis describe a card game.
Take a deck of cards labeled 1, 2, 3, … , n. The deck is shuffled, cards are turned up one at a time and dealt into piles on the table, according to the rule
- A low card may be placed on a higher card (e.g. 2 may be placed on 7), or may be put into a new pile to the right of the existing piles.
At each stage we see the top card on each pile. If the turned up card is higher than the cards showing, then it must be put into a new pile to the right of the others. The object of the game is to finish with as few piles as possible.
The cards are totally ordered using the standard bridge convention, clubs, diamonds, hearts, spades, and I’m counting Aces as high. As a target Aldous and Diaconis recommend aiming for 9 piles, which, combined with an optimal strategy, gives you roughly a 1 in 20 chance of winning. Good luck!
The animation builds on the jQuery Javascript library. I generated the playing card graphics from Ryan Neaveill’s shareware playing card font. If you look at this page’s source you’ll soon realise I haven’t written any Javascript before (not counting copy and paste stuff), and I’d welcome any advice and tips. If you’d like to learn more about this card game and its mathematical properties, have a look at the Aldous and Diaconis paper or read my own notes.