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 |
|
|
|
|