A few days ago I was watching an old re-run of the excellent British television program, QI, and the host of the show made an interesting claim regarding a normal deck of playing cards. He took a new deck, which is ordered by number and suit, and gave it a few shuffles. Afterwards he claimed that no deck of cards had ever before been in that order, as the number of possible orderings was so large that statistically it was (almost) impossible that two randomly shuffled decks could ever be in the same order.

However some viewers have questioned whether the few shuffles that were shown were sufficient to reach all possible orderings. If not, then the number of possible orderings is significantly lower and the claim would be false. So that raises the interesting pair of mathematical problems:

1. How many possible orderings of a deck of cards are there after N shuffles?
2. How many shuffles are required to reach the full 52! possible orderings of a deck of cards?

(For this problem I am defining a shuffle as dividing the deck into two parts, not necessarily equal in size, and then forming one deck again by alternating random numbers of cards from each part. This is what most people refer to as a shuffle, but also includes the possibility of cutting the deck).

The first question is also of interest, as an otherwise excellent combinatorics textbook that I know of gives the wrong answer. I won't embarrass the authors, but their solution actually counts some orderings multiple times and therefore the result they give is too large. As far as I know this problem does not have a simple solution, although clearly it can be solved with a computer simulation.

The second problem is interesting because the number is surprisingly small. In response to the original video I referred to above, some commentators have suggested that the number must be 52 shuffles for the following reason. They argue that one of the possible arrangements is the exact reverse of the starting order - so the first card becomes the last, the second becomes the second-to-last, and so one. And they claim that a single shuffle can only change the relative position of one of these cards. For example a single shuffle can move the first card to the bottom of the deck, but a second shuffle is required to move the second card to the position above it. As such they argue that the position of each card must be changed relative to the next card, and that this would require 52 shuffles. But this is wrong.

In fact every possible ordering can be reached after only six shuffles! If you cut and reassemble the deck only six times, there are 52! = 8.0x1066 possible arrangements of the cards.

Furthermore the proof of this is quite simple, and I will post it here sometime in the future if there is sufficient interest. For now, I would encourage readers to try to prove it themselves and see if they can do better. I do not think that five shuffles is sufficient, but I would be curious to see what other people can do with this puzzle, as well as with the first of the two puzzles.

So I hope you enjoy this puzzle, and find it a rewarding challenge!