juli and I have been talking about Faro or Pharaoh Shuffles, which is a common shuffling technique for card games or magic tricks. It goes like this:
- Divide the 52-card deck into two half-decks of 26 cards, deck A and deck B.
- Merge the two half-decks together so that cards alternate, one from half-deck A, one from half-deck B, but the individual half-decks stay in order.
So if your deck starts out numbered like this:
1, 2, 3, 4, 5, 6, 7, 8 … 49, 50, 51, 52
You divide it into two decks, 1-26, and 27-52, and then merge them together like this:
1, 27, 2, 28, 3, 29, 4, 30, … 25, 51, 26, 52.
If you do this perfectly eight times with a deck of 52 cards, you will get back to the original order. I had trouble believing that, so we sat in a diner and carefully shuffled cards. Six cards return to their original positions after four shuffles. Eight cards take three, twelve takes ten shuffles and three restarts after losing my place.
Of course we both announced we would write a script when we got home, but Juli got hers done first. Go look at it here.
A graph of how many perfect faro shuffles it takes to bring a deck of N cards back into its original order:
And here is an image of the patterns formed by shuffling 52 cards. Each horizontal line is the deck before or after shuffling, and each rectangle is a card. Black is card #1, red is card #52.
What about some other sized decks of cards? Decks that contain a power of two cards return to their original state in log-2 shuffles. Here are the patterns for decks of 16 (4 shuffles), 32 (5 shuffles), 64(6 shuffles), and 128(7 shuffles) cards:
Decks with two more cards than a power of two take twice as many shuffles as the power of two. First the shuffling arranges every card in the deck except the first and last (which never move) in reverse order, then it turns them around again. Here are 18(8 shuffles), 34(10 shuffles), and 66 cards (12 shuffles) card decks:
The slowest decks take two less shuffles than they have cards. Here's 84 (82 shuffles required to return to original state), which does include a "reversed-except-for-the-outside" state, but I don't know how to characterize any of the rest of it.
There is some discussion of the math here, but I wish it went into more detail.