In the children’s card game Snap, a deck of cards is shuffled and divided as evenly as possible among two or more players. In alternating turns, each player deals a card from her stack onto a face-up pile in front of her. If at any time, the top cards of any two players’ face-up piles have the same rank, the first player to shout “Snap!” takes both face-up piles and adds them to the bottom of her remaining stack. The objective is to accumulate all of the cards.
It is possible for the players to deal through their entire stacks without a single snap, i.e., at no time do the top cards of two piles have the same rank. Let us call such a game boring (a term that may be suggested by, say, your niece to whom you are introducing the game). What is the probability of a boring game of Snap?
One of the reasons I love combinatorics is that it is so easy to ask a hard question. That is, we can pose a series of very similar-sounding problems, all of which are easy to state and understand, but whose minor differences result in major changes in complexity of their solutions. The motivation for this post is to describe a simple children’s card game as an example of this phenomenon.
Before tackling the actual problem described above, let’s consider a slightly modified version of the two-player game that is easier to analyze:
- Instead of dividing a single shuffled deck in half, start with two separate complete shuffled decks, one for each player.
- Instead of alternating turns dealing a card from each player’s stack, at each turn both players simultaneously deal a card face-up from their remainder.
Dealing through the entirety of both decks without a snap is effectively equivalent to winning a game of Frustration Solitaire, where a single player deals cards from a single shuffled deck, saying ranks “Ace, two, three, …, king” repeatedly, losing the game if the dealt card ever matches the called rank.
Even within this already-modified context, there are three slight variations that range from very simple to– I think– intractable:
- If a snap requires that both cards match in rank and suit, then we are counting derangements, and the probability of a boring game is approximately , or about 0.367879.
- If a snap requires that both cards match in rank only, as in Frustration Solitaire, then we have discussed this problem before here, in the context of a Secret Santa drawing among 13 families each with 4 family members. In this case, the probability of a boring game is approximately 0.0162327.
- If a snap requires that both cards match in rank or in suit… well, although this is still effectively a problem of counting permutations with restricted positions, I think this problem is much harder in practice, since the board of restricted positions can’t be nicely decomposed into sub-boards with no rows or columns in common.
Let’s consider one more modified version of the game, this time actually rolling back one of the changes above: let’s return to playing with a single shuffled deck divided evenly among the two players, but retain the change where the players deal simultaneously from their stacks.
This version of the game has a lot of structure in common with another children’s card game, War. In this case, a boring game of Snap corresponds to War with no war– that is, dealing through both deck halves without any pair of cards matching in rank.
This is a relatively straightforward inclusion-exclusion problem; with a deck with ranks and suits, the probability of a boring game is
which for a standard 52-card deck yields a probability of a boring game of about 0.210214.
(Edit 2020-09-04: This game is discussed in the Riddler column at FiveThirtyEight.com, where the problem is to compute the probability of not just a boring game of War, but a game where one player wins all of the tricks. If we require a particular player to win all of the tricks, then we can divide the above probability by ; or for the probability of either player winning all of the tricks, divide by .)
Counting “words” with prohibited subwords
Coming back finally to the original rules of Snap, counting boring games is complicated by the fact that the players alternate turning individual cards face-up, rather than simultaneously revealing a pair of cards at a time, so that a snap may “start” with either the first or the second player’s deal. Intuitively, consider skipping the initial separation of the deck into halves, and simply deal cards one at a time from the single shuffled deck; a boring game is one in which no two consecutively dealt cards are the same rank.
There is a wonderful paper by Jair Taylor (referenced below) describing a very general but more sophisticated technique for counting arrangements with these types of restrictions. Applying this technique to Snap, the probability of a boring game using a deck with ranks and suits is
yielding a probability of approximately 0.0454763, or about once every 22 shuffles, that a game of Snap will be boring.
Once again, however, it’s very easy to make this problem much harder: if we allow a snap to involve adjacent cards matching in rank or in suit, what is the resulting probability of a boring game? What if there are more than two players?
- Taylor, J., Counting words with Laguerre series [arXiv]