Thoughts about the Shuffle Problem

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
 
Valid CSS!
 
Valid XHTML 1.1!