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?

Advertisements

Responses

  1. The citizens are the members of the civil society, bound to this society by certain duties, and subject to its authority; they equally participate in its advantages. ,

  2. Many, probably most, of these are chemical engineers or technicians rather than chemists per se. ,

  3. very nice


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: