2
$\begingroup$

A perfect shuffle of a deck of cards can be represented by the following permutation $f\in S_{52}$: $f(x) =\left\{ \begin{array}{ll} 2x-1 & \text{if }x\in\{1,\ldots,26\}\\ 2(x-26) &\text{if }x\in \{27,\ldots,52\} \end{array}\right.$

I'm trying to show that if one performs 8 perfect shuffles of a deck of cards, then this returns the cards to their original position.

What I did was get some cycle decomposition:

(2 3 5 9 17 33 14 27) and (4 7 13 25 49 46 40 28) and

when I tried out starting with 6, I am getting a mess since f(31) = 10, but f(6) = 10

How many other cycle decompositions are there?

  • 1
    the only fixed points are 1 and 52; each cycle will, hopefully, have 2, 4, or 8 elements. So anywhere between 7 and 16. Just go ahead and do it carefully.2012-02-13

1 Answers 1

2

This can be proven, without having to deal with messy cycles.

Notice that the first and last elements are fixed. So we can ignore them.

Now, if you renumber so that 2 becomes 1, 3 becomes 2, etc till 51 becomes 50.

We are interested in a permutation which has the formula

$ x \to 2x \mod 51$

Thus after $n$ steps, we have that

$ x \to 2^n x \mod 51$

Since $2^8 = 1 \mod 51$, you are done.