Cards Reordering

The standard procedure for shuffling a deck of cards is to take the pack face downwards in the left hand and then transfer each card one by one to the right hand, putting the second on top of the first, the third under, the fourth above, and so on until all cards are transferred.

If you perform this operation with an even number of cards and keep on repeating the shuffle in the same way, the cards will in due time return to their original order. Try with 4 cards and you will find the order is restored in 3 shuffles. In fact, where the number of cards is 2, 4, 8, 16, 32, 64, the number of shuffles to get them back to the original arrangement is 2, 3, 4, 5, 6, 7 respectively.

How many shuffles are necessary in the case of 14 cards?

My thought process:

My initial thought takes me back to a math class I took in undergrad about Groups and Rings theory. From what I can remember, that class had a lot of modulus stuff going on.

Let’s write out what the 4 cards in 3 shuffles looks like and see if we can identify a pattern.

Consider 4 cards indexed \(C_{i}\) where \(i = 1, \cdots, 4\)

Base: \(C_1, C_2, C_3, C_4\) First shuffle: \(C_4, C_2, C_1, C_3\) Second shuffle: \(C_3, C_2, C_4, C_1\) Third shuffle: \(C_1, C_2, C_3, C_4\)

I notice that every card in an even index goes above the first card and every card in an odd index goes below so it splits the deck in half and reverses the order as you can see from the Base position to the First shuffle. Because we only have 4 cards meaning we can split the deck in half and have 2 cards in each pile, I think you can only change the order so many times.

I know the problem specified an even number of cards but let’s see with 3 cards.

Base: \(C_1, C_2, C_3\) First shuffle: \(C_2, C_1, C_3\) Second shuffle: \(C_1, C_2, C_3\)

This took only 2 shuffles, the same amount as if we had 2 cards so I think that n and n+1 cards will require the same shuffle if n is an even integer. There’s something beautiful going on with the powers of 2 but what about 6?

Consider 6 cards indexed \(C_{i}\) where \(i = 1, \cdots, 6\)

Base: \(C_1, C_2, C_3, C_4, C_5, C_6\) First shuffle: \(C_6, C_4, C_2, C_1, C_3, C_5\) Second shuffle: \(C_5, C_1, C_4, C_6, C_2, C_3\) Third shuffle: \(C_3, C_6, C_1, C_5, C_4, C_2\) Fourth shuffle: \(C_2, C_5, C_6, C_3, C_1, C_4\) Fifth shuffle: \(C_4, C_3, C_5, C_2, C_6, C_1\) Sixth shuffle: \(C_1, C_2, C_3, C_4, C_5, C_6\)

This took 6 shuffles. This makes me think (hope zealously) that a deck with 14 cards takes 14 shuffles. I think even numbers that are powers of 2 benefit from the implicit binary splitting of the deck, whereas other even numbers can’t split it up quite as nicely.

Let’s see if we can code it before giving up.

Solution:

ahhhh, I was sort of on the right page with groups…. So each shuffle can be represented as a permuation on \(S_{14}\), the symmetric group on 14 integers. In cylic notation, it would look like this: \((1,14,13,11,7,2,12,9,3,10,5,6,4,8)\). And since it is disjoint, this permutation has order 14 meaning 14 shuffles are required.

Takeaways: Abstract algebra kind of slaps. Symmetric groups, disjoint cycles, cyclic permutation. Probably would be useful to brush up on this especially in permutation problems.

deck = [i for i in range(1,15)]
deck
num_shuffles = 0
ordered = False
while not ordered:
    list1 = deck[::2] # bottom half
    list2 = deck[::-2] # top half
    deck = list2 + list1
    print(deck)
    if deck == sorted(deck):
        ordered = True
    num_shuffles +=1

print(num_shuffles)

[14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13]
[13, 9, 5, 1, 4, 8, 12, 14, 10, 6, 2, 3, 7, 11]
[11, 3, 6, 14, 8, 1, 9, 13, 5, 4, 12, 10, 2, 7]
[7, 10, 4, 13, 1, 14, 3, 11, 6, 8, 9, 5, 12, 2]
[2, 5, 8, 11, 14, 13, 10, 7, 4, 1, 3, 6, 9, 12]
[12, 6, 1, 7, 13, 11, 5, 2, 8, 14, 10, 4, 3, 9]
[9, 4, 14, 2, 11, 7, 6, 12, 1, 13, 5, 8, 10, 3]
[3, 8, 13, 12, 7, 2, 4, 9, 14, 11, 6, 1, 5, 10]
[10, 1, 11, 9, 2, 12, 8, 3, 13, 7, 4, 14, 6, 5]
[5, 14, 7, 3, 12, 9, 1, 10, 11, 2, 8, 13, 4, 6]
[6, 13, 2, 10, 9, 3, 14, 5, 7, 12, 1, 11, 8, 4]
[4, 11, 12, 5, 3, 10, 13, 6, 2, 9, 14, 7, 1, 8]
[8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
14