Posted by: rjgage | November 19, 2008

## The Riffle Shuffle, or “If you liked my article review, you’ll love my blog post!”

Hey math fans,

Were you intrigued by the intricate beauty of the group theory behind some card tricks?  Well, what about some more complicated group actions on an entire deck of cards, like perfect shuffles?  You’re in luck, because this blog post is about perfect shuffles.

The most common type of shuffle which performs a group action on an ordered set is called the Riffle shuffle.  In this one, the deck is split exactly in half and the two halfs are combined by interleaving the two halves of the deck.

There are two possible Riffle shuffles: and in-shuffle and an out-shuffle.  In an in-shuffle, each card in the bottom half of the deck is on top of the card in the same position in the top half.  For example, an in-shuffle of the ordered set {1 2 3 4 5 6 7 8 9 10} yields {6 1 7 2 8 3 9 4 10 5}.  In an out-shuffle, just the opposite is true; each card in the top half of the deck goes on top of the card in the same relative position in the bottom half.  Thus, an out-shuffle of the ordered set {1 2 3 4 5 6 7 8 9 10} yields {1 6 2 7 3 8 4 9 5 10}.

So there is some structure here.  Given a deck of 2n cards, we can see that under the out-shuffle, the card in position i will move to the position 2i mod (2n – 1) when the deck is numbered starting with one.  With an in-shuffle, the card in position i will more to the position 2i mod (2n+1) when the deck is numbered starting with zero.

Then how many shuffles does it take to return the deck to its original order and make the entire effort pointless?  For an in-shuffle, this is the multiplicative order of 2 mod (2n+1).  Multiplicative order is a fancy number-theory term for the order of an element of the group Z2n.  For an out-shuffle, this is the order of 2 mod (2n-1).

If you have a deck of 52 cards then, because the order of 2 mod 53 is 52, it will take 52 perfect Riffle in-shuffles to return the deck to the original position.  Because the order of 2 mod 51 is 8, it will take only 8 out-shuffles to return the deck to the original position.  Therefore the ordered set of 52 is invariant under the group actions of 52 consecutive in-shuffles or 8 consecutive out shuffles.

Check out these websites which go into more depth about these things:
Wikipedia
Wolfram’s Math World

Bonus question: what is a really easy invariant property of an ordered set of 52 cards under the group action of a single out-shuffle that one might use in making up a simple magic trick?