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.
14 13 11 7 14 13 11 7 14 13 12 9 3 6 12 11 7 14 13 11 10 5 10 5 10 9 3 6 12 9 8 1 2 4 8 7 14 13 11 7 6 12 9 3 6 5 10 5 10 5 4 8 1 2 4 3 6 12 9 3 2 4 8 1 2 1 2 4 8 1
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.)
( 1 2 4 8 ) ( 3 6 12 9 ) ( 5 10 ) ( 7 14 13 11 )
You will quickly observe that:
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 |
|
|
|
|