A colleague asked this problem.

A perfect riffle shuffle or bridge shuffle is when we split a deck of cards into two halves (one in each hand), and then alternately drop one card from each half till all have fallen. For the sake of this problem, let us assume that the top card will always be the top card and the bottom card will always be the bottom card after shuffling. However the rest of the cards will be deranged.

How many such riffle shuffles do we need to perform on a deck of 52 cards, in order to obtain the exact same starting order?

Such a style of shuffling is also known as out shuffle.

Let us assume that there are 2n cards where n is a positive integer. Let us number the positions of the cards as 0, 1, … 2n − 1 where position 0 is the top of the deck and position 2n − 1 is the bottom of the deck. Here is an example with 10 cards called c0, c1, … c9 with positions indicated in the first column.

0. c0                     c0
1. c1                     c5
2. c2                     c1
3. c3                     c6
4. c4 ———> Shuffling ———> c2
5. c5                     c7
6. c6                     c3
7. c7                     c8
8. c8                     c4
9. c9                     c9
Let us consider a card at position k where 0 ≤ k < 2n. It is easy to see from the description of the problem that a card at position k moves to position 2k if the card belongs to the top half of the deck, otherwise it moves to 2(k − n) + 1.

2(k − n) + 1 ≡ 2k − (2n − 1) ≡ 2k (mod 2n − 1)

So, we can say that a card at position k moves to position k' ≡ 2k mod (2n − 1) after an out shuffle where 0 ≤ k' < 2n.

So, after m shuffles a card at position k moves to position k` ≡ 2m · k (mod 2n − 1) where 0 ≤ k` < 2n. So, we are looking for the smallest positive integer m such that for all integers k, where 0 ≤ k < 2n,

2m · k ≡ k (mod 2n − 1)

Removing k from both sides we get

2m ≡ 1 (mod   (2n−1)gcd(k, 2n−1))

For simplicity, let us represent (2n−1)gcd(k, 2n−1)) as Fnk. So, a card at position k returns to the same position after m out shuffles where m is the smallest positive integer that satisfies the congruence relation

2m ≡ 1 (mod Fnk)

Since 2n − 1 is odd, Fnk must be odd. So, gcd(2, Fnk) = 1. The smallest positive integer m that satisfies the congruence relation above is known as the multiplicative order of 2 modulo Fnk and is denoted as ordFnk(2).

If n = 1, Fnk = 1 and 2m ≡ 1 (mod Fnk) is true for all positive integers m. So, with two cards, an out shuffle doesn't change the positions of the cards.

If n > 2, let us consider a k which is coprime to 2n − 1 and 1 < k < 2n − 1. There exists at least one such k because φ(x) ≥ 2 for x > 2 where φ(x) is the Euler's totient of a positive integer x which is defined as the number of positive integers less than or equal to x that are coprime to x. Now, gcd(k, 2n − 1) = 1. So, now the congruence relation

2m ≡ 1 (mod   (2n−1)gcd(k, 2n−1))

reduces to

2m ≡ 1 (mod 2n − 1)

So, far we understand that after ord2n−1(2) out shuffles, any card at a position number coprime to 2n − 1 would be back to its original position. What about cards at other positions?

For a card at position k such that k is not coprime to 2n − 1, gcd(k, 2n − 1) ≠ 1. In this case the number of out shuffles required to bring the card at its original position is ordFnk2.

2ord2n−1(2) ≡ 1 (mod 2n − 1) ⇒ 2ord2n−1(2) ≡ 1 (mod Fnk) … (since Fnk | 2n − 1)

As a consequence of Lagrange's theorem, ordFnk(2) | ord2n−1(2).

In other words, ord2n−1(2) = c · ordFnk(2) for some positive integer c.

So, performing ord2n−1(2) out shuffles is same as repeating ordFnk(2) out shuffles c times. Every ordFnk(2) shuffles brings back the card at position k to the same position. So, repeating it c times would leave it at the same position as well.

Hence, we conclude that ord2n−1(2) out shuffles would restore a deck of 2n cards to its original configuration, where n is a positive integer.

For a deck of 52 cards, n = 26. So, ord51(2) out shuffles would restore the deck to its original configuration.

Let us compute ord51(2).

From Carmichael's theorem, 2λ(51) ≡ 1 (mod 51), where λ(n) is the smallest positive integer m such that am ≡ 1 (mod n) for every positive integer a coprime to and smaller than n.

λ(51) = lcm(λ(3), λ(17)) = lcm(2, 16) = 16.

Again as a consequence of Lagrange's theorem, ord51(2) | λ(51). In other words, ord51(2) | 16.

Let us check all the factors of 16 and see which one is the multiplicative order of 2 modulo 51.

22 ≡ 4 (mod 51) 24 ≡ 16 (mod 51) 28 ≡ 256 ≡ 1 (mod 51).

∴ ord51(2) = 8.

8 is the answer.

No comments

Post a comment

RSS