From Out Shuffles to Multiplicative Order

From Out Shuffles to Multiplicative Order

Out Shuffles

A perfect riffle shuffle of a deck of cards involves splitting the deck into two halves (one in each hand) and then alternately dropping one card from each half till all cards have fallen. If the shuffling is done in such a manner that the bottom and the top cards remain preserved at their positions, then it is an out shuffle.

Problem

Here is a problem that a colleague asked me recently while discussing shuffling techniques:

Solution

The solution to this problem is rather long, so it has been split into three parts below.

Part 1: Congruence Relation

Let us assume that there are n cards where n is a positive even integer. Let us denote these cards as c0,c1,…,cn−1 where c0 is the card at index 0 (top of the deck), cn−1 is the card at index n−1 (bottom of the deck), and ci is the card at index i where 0≤i≤n−1.

For example, if we have 8 cards, then the cards are denoted as

c0,c1,c2,c3,c4,c5,c6,c7.

After the first out shuffle, these cards are now in this order:

c0,c4,c1,c5,c2,c6,c3,c7.

From the problem description and the example above, we see that after a single out shuffle, a card at index i moves to index 2imod(n−1) for 0≤i<n−1 and the card at index n−1 remains at the same place.

After m shuffles a card at index i moves to index (2mi)mod(n−1) for 0≤i<n−1. The card at index n−1 always remains at the same place.

The solution to the problem then is the smallest positive integer m such that

2mi≡i(modn−1).

for all integers i that satisfy the inequality 0≤i<n−1.

In modular arithmetic, we know that

ac≡bc(modn)⟺a≡b(modn/gcd(c,n)).

where a,b,c, and n are integers. Therefore

2mi≡i(modn−1)⟺2m≡1(mod(n−1)/gcd(i,n−1)).

Let Fni=n−1gcd(i,n−1) where 0≤i<n−1. Now the above congruence relation can be written as

2m≡1(modFni).

Part 2: Multiplicative Order

The smallest positive integer m that satisfies the above congruence relation is known as the multiplicative order of 2 modulo Fni. It is denoted as ordFni⁡(2).

In general, given an integer a and a positive integer n with gcd(a,n)=1, the multiplicative order of a modulo n, denoted as ordn⁡(a), is the smallest positive integer k such that

ak≡1(modn).

In this problem, n is even, so n−1 is odd as a result of which Fni is also odd. As a result, gcd(2,Fni)=1. Therefore, the smallest positive integer m that satisfies the congruence relation 2m≡1(modFni) is denoted as ordFni⁡(2).

If n=2,Fn0=Fn1=1, therefore 2m≡1(modFni) for 0≤i<n−1 and all positive integers m. This proves the trivial observation that when there are only two cards c0 and c1, they remain at index 0 and index 1, respectively, after any number of out shuffles, i.e., their positions do not change with out shuffles.

Case n≥4

If n≥4, we know that there exists at least one integer between 1 and n−1 that is coprime to n−1 because φ(n)≥2 for n≥4 where φ(n) represents Euler's totient of n.

Subcase i is coprime to n−1

For any arbitrary n≥4, let i be an integer that is coprime to n−1 such that 1<i<n−1. Now gcd(i,n−1)=1, so Fni=n−1gcd(i,n−1)=n−1. As a result, ordFni⁡(2)=ordn−1⁡(2). This shows that any card at index i such that i is coprime to n−1 requires a minimum of ordn−1⁡(2) out shuffles to return to its initial place.

Subcase i is not coprime to n−1

For any arbitrary n≥4, now let us consider the case of a card at index i such that i is not coprime to n−1. Since n−1 is odd, we have gcd(2,n−1)=1. Therefore, by definition of multiplicative order,

2ordn−1⁡(2)≡1(modn−1).

Since Fni∣n−1, we get,

2ordn−1⁡(2)≡1(modFni).

This shows that a card at index i such that i is not coprime to n−1 also return to its initial place after ordn−1⁡(2) out shuffles. Actually, it takes only ordFni⁡(2) out shuffles to return the card to its initial place. But ordFni⁡(2)∣ordn−1⁡(2), so ordn−1⁡(2)=cordFni⁡(2) for some positive integer c. Therefore performing ordn−1⁡(2) out shuffles is same as repeating ordFni⁡(2) out shuffles c times. Every ordFni⁡(2) brings back the card to its initial position, so repeating it c times also brings it back to its initial position.

We have shown that a card at index i such that i is coprime to n−1 takes a minimum of ordn−1⁡(2) out shuffles to return to its initial place. We have also shown that a card at other indices also return to its initial place after the same number of out shuffles. Therefore, it takes a minimum of ordn−1⁡2 out shuffles to return the deck of cards to its initial state.

Case n=2

When there are only 2 cards in the deck, every out shuffle trivially returns the deck to its initial state. In other words, it takes only 1 out shuffle to return the deck to its initial state. Indeed ordn−1⁡(2)=ord1⁡(2)=1.

We have now shown that for any positive even integer n, a deck of n cards returns to its initial state after ordn−1⁡(2) out shuffles.

Part 3: Computing Multiplicative Order

For a deck of 52 cards, we have n=52. A minimum of ord51⁡(2) out shuffles are required to return the deck to its initial state. To compute ord51⁡(2) we first enumerate the powers of 2 modulo 51:

20≡1(mod51),21≡2(mod51),22≡4(mod51),23≡8(mod51),24≡16(mod51),25≡32(mod51),26≡13(mod51),27≡26(mod51),28≡1(mod51).

The smallest positive integer k such that 2k≡1(mod51) is 8, so ord5⁡1(2)=8. We need 8 out shuffles to return a deck of 52 cards to its initial state.

---

Home Feed Dark About GitHub Twitter

© 2006–2020 Susam Pal