Our shuffling will generate a permutation of the cards. A permutation is a bijection from a set onto itself. In the case of a deck with index `i = 2n + 1`, the set contains the integers from `1` to `2n`.

Let's look at a series of perfect shuffles for `i = 15`. Remember, this means that the cards that move will be card number 1 through card number 14.

14131171413117141312936121171413111051051093612981248714131176129365105105481243612932481212481

The first column is the starting stack; and each subsequent column is the result of shuffling the previous stack. After four shuffles we are back where we started.

We can decompose the sequence of positions to form a number of cycles. (Just read ACROSS the columns above to see where the cards end up.)

(1248)(36129)(510)(7141311)

You will quickly observe that:

- The cycles are all disjoint (no number appears in more than one cycle); and
- The least common multiple of the lengths of the cycles is
`4`.

The number of shuffles required will always be the least common multiple of the length of the cycles.

Home |

Shuffle Problem |

Initial Ideas |

Permutation |

Cycle Length |

Groups |

Last modified: |

© 2006 |

Peter C. Scott |