Card Shuffling

Achyut Bharadwaj

February 2022

card shuffling, riffle shuffle, modular arithmetic, modular inverse, card tracking, shuffle periodicity

An Interesting Card Trick #

The Problem #

Suppose you have a deck of $52$ cards. You perform a riffle shuffle on these cards. Can you say what the new position of the first card in the deck is, after the shuffle? What about the second card in the deck? The third? In general, is it possible to predict the new position of the $k$th card in the original deck after a new deck is produced through a riffle shuffle?

Suppose instead of $52$ cards, you have $50$ cards. What can you say about the new position of the $k$th card in the original deck? What if you instead had $104$ cards? $102$ cards? $m$ cards, where $m$ is even?

Now, what if you perform $2$ shuffles instead of just one? $3$ shuffles? Can you generalize for $r$ shuffles?

Is there any value of $r$ such that all cards return to their original position? If yes, what is the value of the smallest $r$ required for the deck to return to its original configuration in terms of $m$?

Riffle Shuffle #

The steps for a riffle shuffle are as follows:

Split the card deck into two equal halves
Put the top half of the deck to the left and the bottom half of it to the right ¹
Take a card from the top of the deck on the left and put it down on the table
Take a card from the top of the deck on the right and put this card below the card that is already on the table
Repeat.

Preliminaries #

Modular Arithmetic #

If you have an equation:

(1) $$x \equiv y \pmod n$$

where $x, y, n$ are positive integers, it means that, $n|(x-y)$ ($\equiv$ is an equivalence operator)

If $y$ is $x$ inverse under mod $n$, where $x, y$, are positive integers, it means:

(2) $$xy \equiv 1 \pmod n$$

In other words, when $xy$ is divided by $n$, the remainder is $1$.

$x\equiv y \pmod n$ is just another way of writing $x\mod n = y\mod n$. This implies that $n|x-y$. Also note that while $x\mod n$ is a function, $x\equiv y \pmod n$ is an equivalence relation.

Example #

Find the inverse of $3$ mod $7$.

Sol.

Say, $x$ is the inverse of $3$ under mod $7$. This means that $3x \equiv 1 \pmod 7$. $x=5$ satisfies this.

Order #

The order of $a$ to the base $m$ (represented as $\text{ord}_m(a)$) is defined as the smallest positive integer $n$ such that $a^n\equiv 1 \pmod{m}$.

Example #

Find the order of (WITHOUT A CALCULATOR):

$14$ to the base $197$,
$36$ to the base $197$,
$110$ to the base $197$.

Notice that

(3) $$14^2 = 196 \equiv -1 \pmod{}197$$

So, $14^4 \equiv 1 \pmod{197}$. Therefore the order of $14$ to the base $197$ is $4$.

$36 = 6^2$. So if we find the order of $6$, the order of $36 = 6^2$ will be half of the order of $6$.

After a HUUGEE amount of manual calculation, we get the order of $36$ base $197$ as $36$.

Now, we must find the order of $110$ base $197$. Notice that

(4) $$14\times36 \equiv 110 \pmod{197}$$

Through a lot of calculation, we find the order of $110$ base $197$ as $196$. Notice that $196 = 4\times 49$

Is there a simpler way of finding the order of $110$? Is there a way to generalize this?

Exploring the Problem #

Tricky Example #

Let us take the case of our magic trick. We first number all the cards in the original deck of 52 cards from $0$ to $51$.

First, a guest picks a card from the deck and puts it back in the deck at some random position. Let’s say that this happened to be position $6$ (starting from $0$).

After having performed the riffle shuffle, we put the cards on the table one after the other, starting from card $0$, and stop when we reach card $12$.

Suppose we perform this trick once again, with the guest placing the card at some other position, say $7$. We then see that the new position of the card after the riffle shuffle is $14$.

Some Observations #

Initial Position	Final Position
2	4
6	12
13	26
23	46
31	11
35	19
36	21
7	14

Table-1: Observations #

Generalising Observations #

Suppose the position of the card in the original deck was $k_0$, and the new position after the shuffle is $k_1$.

We observe that, in all the shuffles we tried, the following always holds:

(5) $$k_1 \equiv 2k_0 \pmod{51}$$

A Deck with $m$ Cards #

We generally saw that $k_1\equiv2k_0\pmod{51}$ when the number of cards was $52$, that is when $m=52$.

Suppose we have $m$ cards instead of $52$ cards in the deck. Then, we observe that the position of the card in the new deck ($k_1$) in terms of the position of the card in the initial deck ($k_0$) can be given by: ²

(6) $$k_1 \equiv2k_0\pmod{m-1}$$

Tracking a Card #

Take the $k$th card in the card deck. Our goal is to now find the new position ($k’$) of the card after a riffle shuffle is carried out in terms of $k$.

We saw that $k’ \equiv 2k \pmod{m-1}$, where $m$ is the number of cards in the deck.

We know that $k’\leq m-1$ since $m-1$ is the maximum index of a card in the deck. However, we can show that the equality condition, i.e., $k’=m-1$ does not hold.

Suppose $k’ = m-1$. Then, $m-1 \equiv 0 \equiv 2k\pmod{m-1}$. Therefore, $k\equiv 0\pmod{m-1}$. Hence, $k=0$ or $k=m-1$. If $k=0$, then, when the card deck gets split into a left deck and a right deck, the same card will also be on top of the left deck. Now, during the shuffle, we place the first card of the left deck first, and other cards below it. Therefore, the position of this card continues to remain $0$. Thus, the only option remaining is that $k=m-1$. In other words, the position of the $0$th card and the $(m-1)$st card are always constant.

Hence, for any card that is not the last card (i.e. when $k\neq m-1$), we have $k’ = 2k \mod m-1$ and when $k=m-1, k’ = m-1$.

Periodicity of Shuffles #

We now come to the question: what is the smallest possible value of $r>0$ such that the whole deck returns to its original configuration, where $r$ is the number of shuffles performed?

To answer this, we track the journey of a single card. We ran a computer program with the number of cards in the deck, $m$, as $52$, tracked the card numbered $31$ starting from $0$ and got the following result.

Fig-1: Simulated position of cards for multiple riffle shuffles

Observe that that the position of this card after $r$ shuffles is equal to $31\times2^r \mod m-1$.

The Position of any Card after $r$ Shuffles #

We generally observe that the position of the $k$th card in the deck after $r$ shuffles are performed is given by

(7) $$2^rk \mod m-1$$

provided that $k\neq m-1$. If $k=m-1$, we have seen before that the position continues to remain $m-1$. This can be proven from the fact that the new position after $1$ shuffle is given by $2k \mod m-1$³

Now, suppose that the card returns to its original position after $r_0$ shuffles. Then, we must have

(8) $$2^{r_0}k \mod m-1 = k$$

For this to be true, we must have

(9) $$2^{r_0}k \equiv k \pmod{m-1}$$

Observe that the order of $2$ modulo $52$ is $8$ and so is the periodicity of shuffles. In general, we observe that the periodicity of shuffles with $m$ cards is equal to the order of $2$ modulo $m-1$. We now prove this observation.

Proof #

Suppose the order of $2$ modulo $m-1$ is $n$. We first prove that $r_0\geq n$.

Consider a card of position $p$ where $p$ is co-prime with $m-1$. For this card to return to its original position, we must have

(10) $$2^{r_0}p \equiv p \pmod{m-1}$$

(11) $$p\left(2^{r_0} - 1\right) \equiv 0 \pmod{m-1}$$

Since $p$ is co-prime with $m-1$, we must have

(12) $$2^{r_0} - 1 \equiv 0 \pmod{m-1}$$

Or,

(13) $$2^{r_0} \equiv 1 \pmod{m-1}$$

The smallest natural number $r_0$ such that this is true is when $r_0$ is the order of $2$ modulo $m-1$. Therefore, for a card of position $p$ to return to its original position, we need to perform $n$ shuffles. Therefore, we cannot have $r_0 < n$. This implies that $r_0\geq n$.

Now,

(14) $$2^n \equiv 1 \pmod{m-1} \implies 2^nk \equiv k \pmod{m-1}$$

for some integer $k$. Thus, any card with original position $k$ will return to its original position after $n$ shuffles for any integer $k$. If $r_0 > n$, we have an integer $n<r_0$ such that $2^nk \equiv k \pmod{m-1}$ for all $k$ from $0$ to $m-1$. But we assumed that $r_0$ was the smallest such integer. A contradiction. Thus, $r_0 \leq n$.

We have $r_0 \geq n$ and $r_0 \leq n$. Thus, $r_0 = n$.

Further Generalizations #

$d$–handed Riffle Shuffle #

A $d$ handed riffle shuffle is the same as any other riffle shuffle except that, instead of splitting the deck into two equal halves, we split the deck into $d$ equal portions, and we lay down cards one below the other starting from the top most portion to the bottom most portion.

Similar to a two handed riffle shuffle, in a $d$ handed riffle shuffle, we observe that a relation between the new position of a card, $k_1$, after a shuffle and the original position of the card, $k_0$, is as follows: $$k_1 \equiv dk_0 \pmod{m-1}$$ where $m$ is the number of cards in the deck such that $d|m$. The proof is spread across the next few slides. From this relation, it is easy to derive that the deck will return to its original position after the number of shuffles equal to the order of $d$ modulo $m-1$.

Proof of the Observation #

We initially start with a deck of $m$ cards and split the deck into $d$ equal portions, and lay out the portions left to right. We label the decks from $0$ to $d$. Now, when we lay the cards one by one, we start by first laying the card from deck $0$, followed by deck $1$, and so on till deck $d$. Therefore, the $0$th card of the $n$th partition will be the $n$th card in the new deck for all $n$ ranging from $0$ to $d$ only.

After laying out $d$ cards, we return to deck $0$. Thus, the position of the card with index $1$ in the $0$th deck will be $0+d = d$. The position of the card with index $2$ will be $0+2d = 2d$, and so on. In general, we can say that the position of the card with index $k’$ in the $n$th deck will be $n+dk’$.

Now, consider the $k_0$th card in the original deck. If we can find the corresponding values of $n$ and $k’$ for the $k_0$th card (that is, the partition it is part of and the position of the card in that partition), we will have found the new position of card $k_0$ after a shuffle.

There are $\frac{m}{d}$ cards in each of the $d$ partitions. Therefore, the $k_0$th card can be found in the deck whose index is given by

(15) $$\left\lfloor \frac{k_0}{\frac{m}{d}} \right\rfloor$$

Since there are $\frac{m}{d}$ cards in each of the $d$ partitions, the position of the $k$th card in the partition it belongs may be written as:

(16) $$k' \equiv k_0 \pmod{\frac{m}{d}}$$

Therefore, we can write:

(17) $$k_0 = \frac{m}{d}q +k'$$

for some integer $q$.

Now, the new position of the card is

(18) $$k_1 = n+2k' = \left\lfloor \frac{k_0}{\frac{m}{d}} \right\rfloor + d\left(k_0-\frac{m}{d}q\right)$$

Dividing both sides of $k_0 = \frac{m}{d}q + k’$ by $\frac{m}{d}$, we get

(19) $$\frac{k_0}{\frac{m}{d}} = q + \frac{k'}{\frac{m}{d}}$$

Since $k’$ is the position of the card in a deck of $m/d$ cards, $k’ < \frac{m}{d}$. Thus,

(20) $$\frac{k'}{\frac{m}{d}} < 1$$

This implies that

(21) $$\left\lfloor \frac{k_0}{\frac{m}{2}} \right\rfloor = q$$

Therefore, the new position of the card can be rewritten as:

(22) $$k_1 = q + dk_0 - mq = dk_0 - (m-1)q$$

Taking modulo on both sides of the above, we get:

(23) $$k_1 \equiv dk_0 \pmod{m-1}\quad\quad\quad\blacksquare$$

Another Interesting Problem #

A Problem to Ponder #

Suppose we have a deck of $m$ cards, where $m$ is even, just like before. We split the deck into two equal halves, put the top half to the left and the bottom half to the right.

Just as before, we take the first card from the left deck and put it down. Next, we take the first card of the right deck, but this time, we flip this card upside down before putting it below the card(s) that is/are already on the table. We repeat this process, each time flipping the cards of the right deck.

A question arises: What is the smallest number of shuffles one needs to carry out so that all cards are back to their original flip, that is, the smallest number of shuffles required to ensure that all cards are facing down again?

Progress #

We observed, by running a computer program that the number of shuffles required to bring the deck back to its original flip configuration is either equal to the periodicity of the shuffles itself, or is equal to twice the periodicity of the shuffles.

We have however, not yet been able to prove these observations, and neither have we been able to decipher a pattern as to when the periodicity of flips is twice the periodicity of shuffles and when it is equal to the periodicity of shuffles.

We can also put the bottom half on the left and the top half to the right. This variation of riffle shuffle is called an out-shuffle. ↩︎
We ran a computer program to arrive at this observation ↩︎
To rigorously prove this, we will have to use induction. We will however not be doing so here ↩︎