Recently, I learnt to play a new (to me, and I think newly released) game called Parade. It has an Alice-in-Wonderland theme and framing story, but I'll describe it more abstractly, because the theme is not relevant to this post.
The game has a deck of 66 cards, one each numbered 0 through 10 in each of 6 colours. Game play starts by turning up six cards to form a `parade'. Players then take turns appending a card to the parade, each of which possibly leads to that player picking up earlier cards, based on rules which I'll describe in a moment. There's a scoring system based on the cards each player picks up, but scoring is irrelevant to this post, because this is all about the question: what is the longest the parade can get?
So, how are cards are removed from the parade? When a card is appended, as many earlier cards as equal the number on the new card are `protected'. Everything before the protected cards is vulnerable. The cards that are removed are then those of the vulnerable cards which either (a) match the new card in colour or (b) are less than or equal to the new card in number.
For example, if the parade looks like
9B 2D 5E 7A 1C 8E 6F 6D 7F
(where the colours are A through F and play is at the right end), and we play the 5A, then the protected cards are from the 1C onward (the last five cards, because the played card is a five). Then, of the cards before that (the first four), the 2D, 5E, and 7A are removed, the first two because their numbers are less than or equal to the newly-played five's, the last because it matches the new card in colour. Thus, in this case, the newly played card converts a nine-card parade into seven-card parade.
So, the question: what's the longest the parade can get?
One of the people I learnt the game with was saying it couldn't get longer than 15, which seemed dubious to me. So I wrote a program which generated random shuffled decks and played them out. (Except for the last eight cards, which don't get added to the parade because of a game mechanic I didn't explain above; except for this note, it's irrelevant here.)
This program has now run through some thirteen point six (short-scale) billion shuffled decks and it's found 4234 decks leading to parades of length 16 and 80 of length 17 (I didn't bother printing decks whose longest parade was 15 or shorter).
But then I started looking at them and thinking about it, and I came up with a deck leading to a length-22 parade. Its first 22 cards are
8A 8B 8C 9A 9B 9C tA tB tC 7C tD 7D 7E 6D 6E 5D 5E 0F 1F 2F 3F 4F
(where `t' represents a ten). The rest of the deck is irrelevant, because nothing is picked up when playing any of those 22 cards, leading to the 22-card parade.
I haven't come up with better, but I also haven't proved there isn't anything better. Any thoughts on either?
Edit, 2016-02-28: 81 billion games; 25756 of length 16, 487 of length 17, and 4 of length 18.