Simple City

If you shuffle a deck of cards perfectly eight times, you get back exactly to where you started. Here’s a video of the magician Adam West doing it:

In this post, we’ll see why this works. First let’s tighten up our terminology: a “perfect shuffle” here is really what magicians call a Faro Out-Shuffle: you split the deck in half, and then interleave the two halves. To make things easier, let’s work with a deck of ten cards, initially in numerical order.

Step one: split 1,2,3,4,5 from 6,7,8,9,10.

Step two, interleave the two: 1,6,2,7,3,8,4,9,5,10.

Notice that the outermost cards (1 and 10) remain in place. (That’s why this is an out-shuffle — interleaving the other way produces an in-shuffle.)

At the same time, notice that the card initially in 4th position is now in 7th, and vice versa. We can indicate this in cycle notation by putting the two together in brackets: (4 7).

What about the rest? The card in second position to start with is now in third place, while the card from third position is now in fifth, the card from fifth is now in ninth,… Continuing this line of thought produces the cycle (2 3 5 9 8 6).

So the shuffle is totally described by the collection of cycles (1) (10) (4 7) (2 3 5 9 8 6). (I’ve included the two trivial cycles of length one.)

Now, notice that performing any cycle of length two twice brings us back to where we started: in this case 4 goes to 7 and then back to 4. Similarly, performing a cycle of length 6 six times takes use back to the starting position. In fact then, performing this ten card shuffle six times brings everything back to where it started.

Ok. What about a full 52 card deck? Well, for cards initially in the top half of the deck (i.e. numbered 1-26), the card in (n)th position is moved to ((2n -1))th position after one shuffle, (meaning (1 to 1, 2 to 3, 3 to 5, ldots, 26 to 51)).

For cards in the second half (numbered 27-52), the card in (n)th position is moved to ((2n-52))th position (meaning (27 to 2, 28 to 4, ldots, 55 to 54, 56 to 56 )).

Repeatedly applying the first rule, we can see that 2 goes to 3 which goes to 5 which goes to 9 which goes to 17 which goes to 33. Now applying the second rule, 33 goes to 14 which goes to 27 (by the first rule) which goes back to 2 (by the second rule). Thus we have the cycle:
(2 3 5 9 17 33 14 27).

The same reasoning tells us the other cycles which make up the shuffle, and altogether they turn out to be

(2 3 5 9 17 33 14 27) (4 7 13 25 49 46 40 28) (6 11 21 41 30 8 15 29)
(10 19 37 22 43 34 16 31) (12 23 45 38 24 47 42 32) (20 39 26 51 50 48 44 36)
(18 35) (1) (52)

which is to say six cycles of length eight, one of length two, and the two trivial cycles of length 1. Each of these cycles will take us back to the starting position when applied eight times… as the video above shows!

Question: what if we do a Faro in-shuffle instead? This means interleaving the other way. On ten cards, after one shuffle the deck reads 6,1,7,2,8,3,9,4,10,5. How many applications of this rule are needed to bring us back to the starting position in this case?