My old high school has a program where they invite primary school kids to the school to do science and maths activities – and this year, they asked me to help run one of these, the Mini Mathematicians class. This problem actually came out of a class we did there, on card shuffling.

The basics

This isn’t about all kinds of card shuffling – specifically, it focuses on the riffle shuffle. It’s a little hard to explain over text, but it essentially involves splitting the deck in two, and interleaving the two halves. If done perfectly, so each card is sandwiched between two cards from the other half, then it is a perfect riffle shuffle; and the perfect riffle shuffle is the one we’re interested in.

Next, we need 2 simplifications.

  1. We’re only interested in shuffling even numbers of cards, so that we know the 2 halves are the same size
  2. We only look at in shuffles

What the hell is an “in shuffle”?

Well, when you split the deck into two perfect halves, you have to choose which half (top or bottom) you start with first (noting that you always put down cards from the bottom of each half). If you start by putting down a card from the half that had been on top, then it’s an in shuffle, because you’re moving a card from the middle of the deck to the outside. If you put down a card from the bottom half, then it’s an out shuffle, because the very bottom and top cards stay the same.

Boy, is that confusing. I’ll try and demonstrate it – for example, let’s say I had 6 cards, labelled 1 through 6.

1 
2 
3 
4 
5 
6

I take the cards, and split them into two halves

1 4
2 5
3 6

Now I need to decide which card to put down first (starting with the bottom, so either 3 or 6). If i put down the 6 first, then you put down the 3 from the other side, and keep alternating, ending up with:

1
4
2
5
3
6

Notice how the outer 2 cards, the 6 and the 1, haven’t moved? That means it’s an out shuffle. To do the in shuffle, we would place the 3 down first:

4
1
5
2
6
3

And now all the cards have moved. Keep in mind that we’re interested in the in shuffle, where all the cards move.

Right, onto the good stuff – how many shuffles?

So, you have some even number of cards, N. You start doing your perfect in shuffles. And, before long (unless you chose a large N, in which case it will be after long), you find that the deck… has ended up back in order?

Funnily, if you keep shuffling your cards perfectly, it will eventually return to the original arrangement. This is called resurrecting the deck – doing shuffles until it gets back to the original order. So the question becomes, how many times do you need to do a perfect shuffle to resurrect a given deck?

So, how many is it?

Now it becomes apparent why you need to limit the scenario to perfect in shuffles with even numbers of cards. Adding odd numbers of cards, or out shuffles, or other kinds of shuffles massively increases the scope and complexity of the answer, so let’s just stick to our simpler scenario.

Let’s say we have 6 cards. How many in shuffles till it’s solved?

1 2 3 4 5 6 - initial condition
4 1 5 2 6 3 - shuffle 1
2 4 6 1 3 5 - shuffle 2
1 2 3 4 5 6 - shuffle 3

Ok, so it takes 3 shuffles to get from ordered back to ordered. But splitting the cards in half every time and shuffling them, even mathematically, could get annoying with an arbitrarily large number of cards. Can you make the process shorter?

How to make the process shorter

Let’s start by noting that, if we do the same shuffle, it should send the very top card to the same place every time, regardless of what card that is. In fact, if the shuffle is the same, it will send any card in a given position to the same place.

Look at the shuffle from above more closely:

1 2 3 4 5 6 - initial condition
4 1 5 2 6 3 - shuffle 1
2 4 6 1 3 5 - shuffle 2
1 2 3 4 5 6 - shuffle 3

Notice how a shuffle always sends a card in position 1 to position 2? Similarly, a shuffle always sends a card from position 6 to position 5, and position 4 to position 1, and so on. This means that you can do just a single shuffle, and use it to build a list of functions – an in shuffle sends a card in position 1 to position 2, position 4 to position 1, and so on. Now you know how to go from one row to the next quickly.

Notice how the connections are all the same, even as the colours and cards move around
1 2 3 4
|_|_|_|
/ | | \
3 1 4 2
|_|_|_| 
/ | | \
4 3 2 1
|_|_|_| 
/ | | \
2 4 1 3
|_|_|_| 
/ | | \
1 2 3 4

Now you just shuffle until you get back to the start, the resurrected deck.

That’s nice – you got anything better?

So that helps simplify the process a bit, preventing you from having to write down the two halves next to each other and interleave them manually. It would also help you write a simple computer program to shuffle the cards. But ultimately, it isn’t that much better – it makes shuffling a little bit easier, but then you still have to shuffle the whole deck over and over, until it’s resurrected.

We can improve on this greatly because of one simple trick. Let’s ignore the whole deck of, say, 6 cards, and instead just focus on the first card.

1 2 3 4 5 6
1

Let’s shuffle it, and see where it goes.

1 2 3 4 5 6 -- positions in the deck
1
  1
      1
1
  1
      1

Huh, so there’s a loop – it goes to position 1, then 2, then 4, then 1 again. But when it’s in position 2, where does card 2 go?

1 2 3 4 5 6
  2  
      2
2
  2

So 2 goes 2-4-1-2. What about 4?

1 2 3 4 5 6
      4
4
  4
      4

4-1-2-4. Interesting – so these three cards 1,2, and 4 form a loop, and just cycle through each other’s positions over and over again, in exactly the same order. This means that the deck being shuffled is, in reality, a bunch of individual loops, that each cycle sequentially through each other’s positions before returning to their original position.

If you do this trick with 3,5, and 6, you find that they also cycle between each other as well. So our 6 card deck is, in fact, 2 independent loops:

1-2-4

3-5-6

We can use this fact to tell how many shuffles it takes to resurrect the whole deck. If there are N cards in a loop, and they just go through all the other members of the loop in order, it takes N shuffles to resurrect that loop (feel free to go convince yourself of this fact). So, if shuffling N cards is in fact shuffling a bunch of loops of length n1,n2,n3,…,nk, then the number of shuffles is just the lowest common multiple of all those loop lengths.

for example, 6 cards has 2 loops of length 3:

LCM(3,3)=3

4 cards has 1 loop of length 4:

LCM(4)=4

and generally:

N cards has k loops of lengths  n1,n2,n3,…,nk:

Number of shuffles to resurrect = LCM(n1,n2,n3,…,nk)

That’s good, but can you do it faster?

Gosh, you can’t please some people. Well, yes actually – there’s a way to speed the process of finding these loops up, and this is where the maths really comes into play. Firstly, let’s take a larger number of cards, like 22. Let’s see what happens to card 1:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
1: position 1
  1: position 2
      1: position 4
              1: position 8
                                    1: position 16
                1: position 9
                                          1: position 18
                           1: position 13    1: position 3
          1: position 6
                        1: position 12
1: position 1

It almost looks like a pattern is emerging. Right at the start, it goes from position 1, to 2, to 4, to 8, to 16 – doesn’t this look a lot like the powers of 2? unfortunately, it stops after that. Does that mean the pattern was just a fluke? Actually, no – if you keep following the shuffle, you find that the doubling continues, but if the card position is too large to fit into the deck, it wraps back around to the start. To see this, it helps to be familiar with something called a mod function.

A mod function is basically a remainder function after division – it does division, throws away the answer, and keeps the remainder. For example:

8 mod 5 = 3

11 mod 4 = 3

20 mod 10 = 0

This is also written as 8%5=3, or 11%4=3.

So, what’s the pattern? well, if you have deck of C cards, and you want to know where card P is after N shuffles:

Position = P*2N mod (C+1)

So, for the example above, P=1 (starts with card 1), C=22.

1*20 mod 23 = 1

1*21 mod 23 = 2

1*22 mod 23 = 4

1*23 mod 23 = 8

1*24 mod 23 = 16

1*25 mod 23 = 9

1*26 mod 23 = 18

1*27 mod 23 = 13

1*28 mod 23 = 3

1*29 mod 23 = 6

1*210 mod 23 = 12

1*211 mod 23 = 1

So we know that there is 1 loop of 11 cards when shuffling 22 cards. To find the other loops, simply pick some card not in that loop (say, 5) and then repeat this process – if you do, you’ll find there is another loop of 11 cards. Since there are 22 cards, all the cards are accounted for in one of those two loops – and since the lowest common multiple of 11 and 11 is 11, that’s how many shuffles it takes to resurrect 22 cards.

Woah, that got complicated

Sorry about that – if you couldn’t get through that convoluted explanation, just know that there is a general formula to find where a given card goes after N shuffles:

Position after N shuffles = P*2N mod (C+1)

where the card starts at position P, and there are C cards in the deck. The list of positions it throws out tells you the list of cards in that loop. To find the next loop, just go to the first card that’s not in the loop, and repeat.

So, how do you go from this formula to the specific number of shuffles it takes to resurrect that C card deck?

Admission time – I genuinely don’t know. As it turns out, that problem is actually really hard to solve – in fact, it turns out to be linked to the factorisation of large numbers, which is a famously difficult problem.

What does this have to do with factorising?

To find how long a loop is, we essentially want to solve this equation –

P*2N mod (C+1) = P

we can rewrite this as:

P*2N -P = Q*(C+1)

P(2N -1)=Q*(C+1)

where N is number of shuffles, P is the starting position of the card, C is the number of cards, and Q is some random integer that we’d like to find.

Basically, what this boils down to is that we want to find all the N where (2N -1) is an integer multiple of (C+1); essentially, we need to be able to factorise (2N -1), which gets very difficult very quickly.

Other interesting tidbits

Even though the number of shuffles is hard to determine, there are tantalising hints of patterns – for example, here’s a plot of number of cards vs number of shuffles to resurrect:

ShufflePattern

There are a bunch of interesting features

-Why is there a big gap, roughly between y=x/2 and y=x, where only a few dots lie?

-Why are there some highly concentrated lines?

-Why are there always dots clustered around 0?

-Why is there a common line where the number of shuffles equals the number of cards?

but the most interesting feature is that the number of shuffles never seems to exceed the number of cards. I have no clue why.

Advertisements