TAOCP 3.4.2 Exercise 13

Let the positions of the cards be numbered modulo $2n-1$.

taocpmathematicsalgorithmsvolume-2

Section 3.4.2: Random Sampling and Shuffling

Exercise 13. [**] [M23] (S. W. Golomb.) One of the most common ways to shuffle cards is to divide the deck into two parts as equal as possible, and to "riffle" them together. (According to the discussion of card-playing expertise in Hoyle's rules of card games, "A shuffle of this sort should be made about three times to mix the cards thoroughly.") Consider a deck of $2n - 1$ cards $X_1, X_2, \ldots, X_{2n-1}$; a "perfect shuffle" $s$ divides this deck into $X_1, X_2, \ldots, X_n$ and $X_{n+1}, \ldots, X_{2n-1}$, then perfectly interleaves them to obtain $X_1, X_{n+1}, X_2, X_{n+2}, \ldots, X_{n-1}, X_n$. The "cut" operation $c$ changes $X_1, X_2, \ldots, X_{2n-1}$ into $X_{n+1}, X_{n+2}, \ldots, X_{2n-1}, X_1, \ldots, X_n$. Show that by combining perfect shuffles and cuts, at most $(2n-1)(2n-2)$ different arrangements of the deck are possible, if $n > 1$.

Verified: yes
Solve time: 1m12s

Let the positions of the cards be numbered modulo $2n-1$. A perfect shuffle sends position $i$ to $2i \pmod{2n-1}$, because the order

$$ X_1,X_{n+1},X_2,X_{n+2},\ldots,X_{n-1},X_{2n-1},X_n $$

places the card originally in position $i$ into position congruent to $2i$ modulo $2n-1$. The cut operation sends position $i$ to $i+n \pmod{2n-1}$. Thus every arrangement obtainable from cuts and perfect shuffles corresponds to a permutation of the form

$$ i \mapsto 2^a i+b \pmod{2n-1}, $$

for some integers $a\ge0$ and $b$, since compositions of the maps $i\mapsto2i$ and $i\mapsto i+n$ generate only affine transformations modulo $2n-1$.

There are at most $2n-1$ possible values of $b$. The multiplier $2^a$ depends only on $a$ modulo the order of $2$ in the multiplicative group modulo $2n-1$; this order is at most $\varphi(2n-1)\le 2n-2$. Hence there are at most $2n-2$ distinct multipliers $2^a$. Therefore the number of distinct affine transformations $i\mapsto2^a i+b$ is at most

$$ (2n-1)(2n-2). $$

Since every arrangement obtainable by combining perfect shuffles and cuts arises from one of these transformations, at most $(2n-1)(2n-2)$ different arrangements of the deck can occur when $n>1$.

$$ \boxed{(2n-1)(2n-2)} $$

∎