4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $32!$ will certainly do it anyway! $\endgroup$ – JP McCarthy Oct 15 '14 at 12:57
  • $\begingroup$ Yeah, right. Should have added that it is the minimum number of shuffles I'm looking for... Proving that would be a bit harder, I guess. $\endgroup$ – A. Breust Oct 15 '14 at 12:58
  • $\begingroup$ Ah Breust, my comment was but in gest! $\endgroup$ – JP McCarthy Oct 15 '14 at 13:57
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This needs a tweaking. We need $f(1)=1$ but with this you have $f(1)=2+1=3$... $\endgroup$ – JP McCarthy Oct 15 '14 at 18:09
  • $\begingroup$ No it's a typo, it should have been $f(i)=2i-1 \pmod{(2^n-1)}$ $\endgroup$ – Marc Bogaerts Oct 15 '14 at 18:13
  • $\begingroup$ I had something like this and failed to implement it as easily as you. I think what happened was that I had a piecewise definition mod something and didn't quite realise I could do it in one go and do my mod stuff later. I am very happy with my answer but to be honest yours is just way more straightforward so I am compelled to give you plus one! $\endgroup$ – JP McCarthy Oct 15 '14 at 18:18
  • $\begingroup$ Very fair! I had the luck to program the stuff and to see what really happens without the mod. Then I went to see what exactly went on 'at the end' of the orbit. I haven't looked at the arbitrary case yet but it could be very interesting. $\endgroup$ – Marc Bogaerts Oct 15 '14 at 18:36
  • 1
    $\begingroup$ I kind of like this answer but, however, there is something bothering me. How can you have $\pmod{(2^n-1)}$ if your indexes go to $2^n$? I mean, you're mapping $2^n$ numbers into $2^n-1$... or do I miss something? $\endgroup$ – A. Breust Oct 16 '14 at 7:20
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.