52 card pickup

This is a fun little puzzle. You have a deck of 52 playing cards, and you hand them all to your young niece. Your niece, thinking it hilarious, throws the entire deck high into the air and the cards flutter down and scatter over the floor in a random mix of face-up and face-down cards.

(Because they got thrown high into the air, we are going to assume that each card, individually, has a 50:50 chance of landing face-up or face-down).

You collect them all together back into a stack but discard all the cards that landed face-up.

You hand this, shorter, stack back to your niece, and she repeats her trick of throwing them up into the air and scattering them. Again, you collect them and discard the face-up cards, handing those that remain back to her.

You repeat this process until all the cards have been discarded. What is the expected number of rounds this game will take?

This is one of those great problems that is fun to model. In just a few minutes you can write a few lines of code to simulate the tosses with random numbers, and count the number of throws required. Then, Monte-Carlo style, you can run your simulation a few million times to get a really good approximation for the expected number of throws. I have to admit, this is how I first approached the problem, and I obtained the answers which I used to confirm that my mathematical analysis was correct.

I can think of some canonical variants of this puzzle. If, instead of cards, you had a bucket of coins and flipped them in rounds, and on each round you discarded all those that landed tails. How many rounds would it take you to empty your bucket? Maybe you have a birthday cake adorned with ‘trick’ candles, and after blowing them out, each candle has a 50:50 chance of re-lighting. What is the expected number of blows to extinguish all the candles?

This is a recursive problem. A large number of cards reduces to a smaller set, then to a smaller set, all the way down. We can solve this by starting at the base case and working our way up. (A 52 card game reducing to a 32 card game, is no different from that point onwards as a game that started with 32 cards).

The base case is when we have one card. If we only have one card, what is the expected number of trials? There are only two things that can happen when we throw one card. Either it lands face-up (game over), or it lands face-down, and we are back to where we started. We can write a formula for this.

If we say that E(x) is the expected number of turns when there are x cards remaining, then here is the formula for E(1).

There is a probability of ½ that it will land face-up (game over), and this takes one move. Or, there is a probability of ½ that is will land face-down and this will have taken us one move and we’re back to where we started. The formula is self-referential. With a little algebra we can re-arrange and see that the expected number of turns when there is only one card left is 2 (from here on out, I’ve used E₁ instead of E(1) as the nomenclature to described the expected number of moves as it is easier to read!)

Next let’s consider what happens when there are two cards left. One of three things could happen:

Writing this as a self-referential formula for E₂, we can substitute in the value for E₁ = 2 that we already calculated and obtain the solution for E₂ = 8/3.

Similarly, when we have three cards left, we can have all three land face-up, have two land face-up, one land face-up, or none land face up.

Again we can write a formula, and substitute, as appropriate, the solutions we already know for E₂ and E₁.

This gives a result for E₃.

And so for E₄ …

And E₅ …

If you are familiar with the binomial theorem, you’ve probably spotted the pattern by now, with the parameters representing the binomial coefficients for the number of combinations. In no surprise to anyone, these can also be found in Pascal’s Triangle

Generically, there is a formula for the expected number of trials it will take to finish the game starting with n cards:

Cutting to the chase, here are all the results in tabular form. On the left is the number of cards. In the middle is the expected number of turns (in rounded decimal form), and on the right is the exact answer if you want to do the division.

We can see from this that the expected number of turns to complete 52 card pick is, mercifully, just a hair over seven tosses.

Here is the data plotted in graph format.