The Perfect Shuffle

[天天]

     There are two different ways of defining a perfect shuffle. Both ways involve splitting the 52 card deck exactly in half and then "interweaving" the two halves so that cards in odd positions are from one half and the cards in even positions are from the other half. The two ways of perfectly shuffling have, respectively, ABABABAB... and BABABABA... configurations, where A = from the top 26 of the deck and B = from the bottom 26.

 

The perfect shuffle that Marilyn is presumably talking about (whether she in fact knows this or not) is the ABABABAB... shuffle. Enumerate the cards 1 to 52 from the top to the bottom of the deck. We get the following equations:
if 1<=x<=26, then x -> 2x-1 (card in position x goes to position 2x-1)
if 27<=x<=52, then x -> 2(x-26) = 2x-52
Notice that 2x-1 = 2x-52 modulo 51. Therefore, we can merge these two equations into this Fundamental Equation:

 

x -> 2x-1 mod 51

 

At first, you may say, "Wait! 1=52 mod 51, and that creates a problem." In fact, it doesn't because it's obvious that the 1 card stays in the 1 position throughout, so there's no chance of a mix up.

 

Now, we want to know what the Fundamental equation gives after 8 iterations.

 

1 iteration: 2x-1
2 iterations: 2(2x-1)-1 = 4x-3
3 iterations: 2(2(2x-1)-1)-1 = 8x-7
n iterations: (2^n)x - (2^n -1)
8 iterations: 256x - 255

 

What happens when we take 256x-255 mod 51? Poof! - we get x again. Does this make me a magician?
Different Decks

 

I'm getting that 64 doesn't work. I went back to "Marilyn is Wrong," where you noted that 2 shuffles works for 4 cards, 3 shuffles for 8, and 4 for 16. This is all correct. Continuing this series, you should have computed 6 shuffles for 64 (since 64 = 2^6) and 8 shuffles for 256 (since 256 = 2^8). In general, n shuffles works for 2^n cards using the AB shuffle. From now on I will use these definitions, where n is even:
AB shuffle

 

(1,2,...,n/2)->(1,3,...,n-1) (top half to odd numbers) and
(n/2+1,n/2+2,...,n)->(2,4,...,n) (bottom half to even)

 

BA shuffle

 

(1,2,...,n/2)->(2,4,...,n) (top half to even) and
(n/2+1,n/2+2,...,n)->(1,3,...,n-1) (bottom half to odd)
AB Shuffle

 

For the AB shuffle we get the following 2 formulas:
if 1 <= x <= n/2, then x -> 2x-1
if n/2+1 <= x <= n, then x -> 2x-n
Now we can make things a lot easier for ourselves by taking everything modulo n-1. Modulo n-1, the 2 formulas are equivalent, giving:

 

x -> 2x-1 mod n-1 (since 2x-1 = 2x-n mod n-1)

 

k iterations of the shuffle sends x to
(2^k)x - ((2^k)-1) = x + ((2^k)-1)(x-1) mod (n-1).

 

We can prove this by induction:

 

1 iteration sends x to 2x-1 mod n-1 = x + ((2^1)-1)(x-1).
Assume k-1 iterations send x to x + ((2^(k-1))-1)(x-1) mod n-1.
Then k iterations send it to 2(x+((2^(k-1))-1)(x-1))-1 mod n-1
=2x + 2*(2^(k-1))(x-1) - 2(x-1) - 1
= x + ((2^k)-1)(x-1) mod n-1.

 

Basically we want to know what combinations of k (iterations) and n (cards) return the deck to its original position. Equivalently we want to know the (k,n) such that x = x + ((2^k)-1)(x-1) mod n-1 for all x, 1<=x<=n.

 

This gives:
((2^k)-1)(x-1) = 0 mod n-1 for all x,
meaning n-1 divides ((2^k)-1)(x-1) for all x.

 

So we conclude that n-1 divides (2^k)-1. This is a necessary and sufficient condition for k AB shuffles to work on n (even) cards.

 

8 shuffles works for 52 cards because 52-1 = 51 divides (2^8)-1 = 255. We can easily find other card quantities for which 8 AB shuffles will return the card to their original order by taking all the divisors of 255 and adding 1 to them. This gives 2, 4, 6, 16, 18, 52, 86, and 256 as deck sizes for which eight AB shuffles returns the deck to its original order.
BA Shuffle

 

Notice that when you AB shuffle n (even) cards, you BA shuffle the n-2 middle cards (all the cards except the top and bottom ones). Therefore, if k AB shuffles work for n cards, k BA shuffles work for n-2 cards. This gives 2, 4, 14, 16, 50, 84, and 254 as deck sizes for which eight BA shuffles returns the deck to its original order. Overall, decks with 2, 4, 6, 14, 16, 18, 50, 52, 84, 86, 254, and 256 cards can return to their original order upon being perfectly shuffled 8 times.