Susam Pal

A colleague asked this problem.

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 c₀, c₁, … c₉ 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

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` ≡ 2<sup>m</sup> · 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,

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

Removing k from both sides we get

2^m ≡ 1 (mod   ⁽²ⁿ⁻¹⁾⁄_{gcd(k, 2n−1)})

For simplicity, let us represent ⁽²ⁿ⁻¹⁾⁄_{gcd(k, 2n−1)}) as F_nk. 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

2^m ≡ 1 (mod F_nk)

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

If n = 1, F_nk = 1 and 2^m ≡ 1 (mod F_nk) 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

2^m ≡ 1 (mod   ⁽²ⁿ⁻¹⁾⁄_{gcd(k, 2n−1)})

reduces to

2^m ≡ 1 (mod 2n − 1)

So, far we understand that after ord_2n−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 ord_Fnk2.

2^{ord_2n−1(2)} ≡ 1 (mod 2n − 1) ⇒ 2^{ord_2n−1(2)} ≡ 1 (mod F_nk) … (since F_nk | 2n − 1)

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

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

So, performing ord_2n−1(2) out shuffles is same as repeating ord_Fnk(2) out shuffles c times. Every ord_Fnk(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 ord_2n−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, ord₅₁(2) out shuffles would restore the deck to its original configuration.

Let us compute ord₅₁(2).

From Carmichael's theorem, 2^λ(51) ≡ 1 (mod 51), where λ(n) is the smallest positive integer m such that a^m ≡ 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, ord₅₁(2) | λ(51). In other words, ord₅₁(2) | 16.

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

2² ≡ 4 (mod 51) 2⁴ ≡ 16 (mod 51) 2⁸ ≡ 256 ≡ 1 (mod 51).

∴ ord₅₁(2) = 8.

8 is the answer.