Experiment № 094 · The story
The Leftmost Pile
Why I picked it
I had done a sort (quicksort) and a dynamic program (edit distance), but never the problem that sits between them: find the longest run of cards, not necessarily adjacent, that only goes up. There are 2n subsequences to check, and the textbook answer is a quadratic table. Then there is this: a solitaire game, played in the 1960s and written up by Colin Mallows, in which you just deal cards onto piles and count the piles at the end. It is the same answer, in n log n, and nobody has to remember anything but the top cards. Git's "patience diff" still uses it to line up unique lines between two files.
What I enjoy about it
The proof fits in two sentences, and you can watch both of them. Every pile runs downhill, top to bottom, so a climb can never use two cards from the same pile: there are at least as many piles as the longest climb. And each card keeps one pointer to whatever was on top of the pile to its left when it landed, so following pointers back from the last pile walks a climb that touches every pile: at most as many piles as the climb. Those are the coloured downhill strands and the one bright uphill line in the top chart. Two different questions, "how few falling piles can I deal into?" and "how long a rising chain is hidden here?", turn out to have one number between them.
Then the second mode surprised me more than the first. Shuffle a deck of n and the climb is almost always close to 2√n, which Vershik, Kerov, Logan and Shepp proved in 1977, answering a question Ulam asked in 1961. The leftovers, shrunk by n1/6, settle into the Tracy–Widom shape that also describes the largest eigenvalue of a big random matrix (Baik, Deift and Johansson, 1999). A card game and random matrices draw the same lopsided bell.
Something you might take away
When the best thing is too expensive to search for, look for the matching smallest thing on the other side. Any way of splitting the deck into falling piles caps the climb, and any climb proves you need that many piles. When the two meet, each one proves the other is optimal, and you can stop looking. Greedy got there by always choosing the leftmost pile that fits, which leaves the most room for the cards still to come.