Silly Cycles

Now all we have to do is figure out the least common multiple of the lengths of the cycles! I wrote a C program to calculate the cycles for deck with indices from 3 to 201. The program displays the actual cycles for decks up to index 51 and then just lists the lengths of the cycles thereafter. The data generated shows an interesting fact: the length of the first cycle (the one containing card number 1, the bottom card) is ALWAYS the least common multiple of the lengths of all the cycles.

Claim 3: We only need to find the length of the first cycle.

Claim 3.1: No other cycle can will ever be longer than the first cycle. Suppose the first cycle has length m+1. That cycle will therefore be: ( 1 2 4 8 ... 2m ), all mod i of course.

Now let's look at the cycle beginning with with some number k, not in the cycle starting with 1. The first m+1 elements in this second cycle will be ( k 2k 4k 8k ... 2mk ) all mod i of course.

We know that 2m+1 mod i = 1, so there exists some number r such that 2m+1 = ri + 1. So 2m+1k = k(ri+1) = rki + k making 2m+1k mod i = k. Therefore, that cycle must also end, since we have arrived at the beginning.

Claim 3.2: The length of every other cycle must divide the first cycle. Suppose the length of the cycle for k does NOT divide the length of the cycle for 1. Then the k cycle will not produce k when the shuffling is repeated for the length of the 1 cycle. This contradicts our observation that any cycle for k will repeat at the length of the cycle for 1.

Finally, we can observe that for a deck with index i = 2n + 1, the cycle containing card number 1 will have length x where x is the smallest number such that 2x mod i = 1.

We have made a lot of progress; we have reduced the problem to what seems like a relatively straightforward calculation. Nevertheless, I want to see if we can find something a bit more elegant.

 
Home
 
Shuffle Problem
Initial Ideas
Permutation
Cycle Length
Groups
 
Last modified:
 
© 2006
Peter C. Scott
 
Valid CSS!
 
Valid XHTML 1.1!