The Perfect Shuffle Problem

Suppose you have a deck containing an even number of cards.

Now, there are two ways to accomplish the "perfect shuffle" referred to in the middle step.

  1. Make the bottom of the TOP half of the deck the bottom of the shuffled deck.
    This results in the top of the bottom half becoming the new top.
  2. Make the bottom of the BOTTOM half of the deck the bottom of the shuffled deck.
    This results in BOTH the bottom and top cards staying put.

These shuffles actually result in the same problem, but with a small twist. If you perform shuffle 1 with say x number of cards, you will equivalently be doing shuffle 2 with (x+2) cards and simply ignoring the top and bottom cards (which never change position.)

I have recently learned that the perfect shuffle I described is called a riffle shuffle or Faro shuffle, and that shuffle 1 is called an "in-shuffle" and shuffle 2 is called an "out-shuffle."

We will define a "shuffle index" which I will usually refer to as simply "index" or even "i" for short as follows:

This way, we do not have to decide which way is "right." Just pick a shuffle method, factor in the number of cards, and we get an index. That choice for an index has some very nice properties, as we shall see.

We will number the cards starting from the bottom of the deck.

As a result, the cards that move in either case will be card number 1 through card number (i-1). (Card 0, the bottom card in shuffle 2, does not move, and card i, the top card in shuffle 2, likewise does not move. Neither card exists in shuffle 1.) This helps show why the shuffle type does not really matter.

Now we are ready to ask a few questions. These questions assume a deck with an even number of cards whose index is therefore odd.

  1. Do you always return to the starting position after a certain number of shuffles, no matter what size index you are using? (The answer is "yes" and the number of shuffles is always less than the index.)
  2. Given a deck with index i > 2, can we figure out an easy way to calculate how many shuffles are required to return to the starting position?
  3. Given any integer k > 1, is there always a deck such that k shuffles returns the deck to the starting point?
  4. For all indices greater than some arbitrary I, what is the least number of shuffles that will return some one of the corresponding decks to the starting point?
 
Home
 
Shuffle Problem
Initial Ideas
Permutation
Cycle Length
Groups
 
Last modified:
 
© 2006
Peter C. Scott
 
Valid CSS!
 
Valid XHTML 1.1!