How many perfect shuffles are needed to go back to initial state?

Question

The other day, in a popular-science book, I saw:

Given 32 cards ($c_i$ for $i=0..31$), cut the deck into two parts and shuffle them the American way (riffle shuffling). The deck now looks like: $c_0, c_{16}, c_1, c_{17}, \dots, c_{15}, c_{31}$.

The fact is, by repeating this shuffle 5 times in total, you will go back to the initial ordered state of the deck. Some close-up magicians can use this result to pretend having a randomly shuffled deck.

I found that really cool, but, somehow, I needed to prove it. Looking for simple example as a starting point I got that for a 4-card-deck, it's easy to see that you only need two shuffles: $$(c_0,c_1,c_2,c_3)\rightarrow(c_0,c_2,c_1,c_3)\rightarrow(c_0,c_1,c_2,c_3)$$

The generalized version I came up is what I want to prove: For $2^n$ cards, you need $n$ shuffles to go back to the initial state.

Recursion?

I wanted to do it by recursion, and I got stuck pretty soon. The only useful (I hope) tool I found is an algebric representation of the shuffling. If the current state of the deck is ($c_i$ for $i=0..2^n$), then after shuffling it will become ($c_{f(i)}$ for $i=0..2^n$), with: $$f(i) = 2^{n-1} i + \left\lfloor\frac{i}{2}\right\rfloor \pmod{2^n}$$

With this tool, I "only" have to prove $\forall i, f^n(i) = f\circ f \circ \dots \circ f(i) = i$.

Does anyone can help me to prove this theorem?

---

And, as suggested, it would be awesome to prove that this is the minimum number of times needed.

Edit: There has been a lot of work as the references of this sequence. This is the generalized case (not only $2^n$ cards). I think this is a good thing to look at.

Answer 1

Your tool is almost right. The idea is to work with the reversed shuffle. That is to say $(c_0,c_1,c_2,c_3,c_4,c_5,c_6,c_7)\rightarrow(c_0,c_2,c_4,c_6,c_1,c_3,c_5,c_7)$.

The last card $c_{2^n-1}$ never move. For the other cards, you can find the recursion formula $f^{-1}(i)=2i \pmod{(2^n-1)}$. So we have

$$\begin{align} (f^{-1})^n(i) & =2^ni & \pmod{(2^n-1)}\\ &=(2^n-1)\times i+i&\pmod{(2^n-1)}\\ &=i&\pmod{(2^n-1)} \end{align}$$

So, we proved it for the reversed shuffle! (And, consequently, for the initial shuffle $f$).

Now to see that $n$ is the order of $f^{-1}$ and not a divisor of $n$ we observe how the cyclic group generated by $f^{-1}$ acts on the numbers $(1,\ldots,2^n-1)$. The orbits have all size a divisor of $n$. Now to prove that there is actually an orbit of order $n$ we note that this is the case for the orbit of $1$. Indeed we have that this orbit is $1,2,2^2,\dots, 2^{n-1}$. These are all $< 2^n-1$ so all different modulo $(2^n-1)$ and there are exactly $n$ of them.

Answer 2

Let the card positions be given by $i\in\{0\}\cup[2^n-1]$.

Define an invertible map $x:\{0\}\cup[2^n-1]\rightarrow [0,1]$ by $$x(i)=\frac{i}{2^n-1}.$$

Now you can show that where $\sigma$ is your riffle shuffle, that

$$\sigma(i)=x^{-1}(D(x(i)))\Rightarrow \sigma^N(i)=x^{-1}(D^N(x(i))),$$

where $D:[0,1]\rightarrow [0,1]$ is the Doubling Mapping $$D(x)=2x\mod 1.$$

Note that

$$x(i)=\frac{i}{2^n-1}=\frac{2^{-n}i}{1-2^{-n}}=\sum_{k=0}^\infty2^{-n}i(2^{-n})^k,$$ is recurring in binary so that

$$x(i)=(0.\overline{a_1a_2\dots a_n})_2,$$

where $\displaystyle(0.a_1a_2\dots a_n)_2=\frac{i}{2^n}$.

It is easy to show that

$$D((0.b_1b_2\dots b_n)_2)=(0.b_2b_3\dots b_n)_2.$$

Now if you have all of that you have

$$D^n(x(i))=x(i),$$

because of the recurring nature of $x(i)$. Hence we would have

$$\sigma^n(i)=x^{-1}(x(i))=i,$$ for all $i\in\{0\}\cup [2^n-1]$ and you would be done.

I think the orbit-stabiliser theorem for $G=\langle\sigma\rangle$ acting on $X=\{0\}\cup[2^{n}-1]$ will show that $n$ is a minimum... by looking at the fixed points of $D^n$... For example, $x=(0.\overline{100\cdots001})_2$. This has only one stabiliser --- $\sigma^n$ but $n$ elements in the orbit so that $|G|=|\text{orb}(x)||\text{stab}(x)|=n\cdot 1=n$ so that $\text{o}(\sigma)=n$.

Answer 3

This has an answer with references at http://mathworld.wolfram.com/Out-Shuffle.html