We first need to explore what happens to each card after one shuffle. Suppose we are given a deck with index `i`. We will ignore the cards that do not change position, if we are doing shuffle 2.

Claim 1: Card number `k` becomes card number `(2k mod i)`.

Since `i` must be odd, there is some number `n` such that `i = 2n + 1`.

It is easy to see that the cards in the bottom half of the deck will become the even-numbered cards. They will each be located at the position exactly twice as high as they started. Card number `n`, the top card in the bottom half, becomes card number `2n = i-1`, the top card overall.

The cards in the top half will become the odd-numbered cards. Look at the bottom card in the top half, card number `(n+1)`. We know it will become the bottom card after the shuffle, card number `1`. Recall that `i = 2n + 1` and observe that:

2(n+1) mod (2n+1)= (2n+2) mod (2n+1)= [(2n+1) + 1] mod (2n+1)= [(2n+1) mod (2n+1) + [1 mod (2n+1)]= 0 + 1= 1

The rest of the cards in the top half will fall neatly in line after this card.

Claim 2: Our calculation, `[2k mod (2n+1)]`, will always generate a number between `1` and `2n`, inclusive.

The number will always be less than or equal to `2n` because we are taking the number modulus `(2n+1)`. It can never generate `0` since `2k` is even and `(2n+1)` is odd. The first `n` cards will generte the even numbers in order; the second `n` cards will generate the odd numbers in order.

Home |

Shuffle Problem |

Initial Ideas |

Permutation |

Cycle Length |

Groups |

Last modified: |

© 2006 |

Peter C. Scott |