1
$\begingroup$

How many times do we need to perfectly shuffle a deck of 2n cards for them to return to their original order.

for $n=3$ we have the permutation $(142)(356)$

I am interested when 2n+1 is prime. Here is how far I have got:

let $a$ denote the position of a card. then what we are trying to find is the minimum x such that: $2^xa=a ($mod$2n+1)$

as we are only interested in when 2n+1 is prime we are looking for the multiplicative order of 2 mod $2n+1$

Case 1:

$p=2n+1$ where $n$ is prime and $n=3($mod$4)$

if we have the prime $p=2n+1$ where $n$ is prime and $n=3($mod$4)$ -> $p|2^n-1$

proof of above theorem http://en.wikipedia.org/wiki/Mersenne_prime

so the order of such a deck of 2n cards is $n$ eg $23=2*11+1$ then $2^{11}=1 ($mod$23)$

Case 2: $p=2^q-1$ then order is $q$

case 3: $p=2^q+1$ then order is $2q$

After this i thought that all other orders of 2 would just be $2n$ by fermats little theorem but this is not the case as take $2n = 102$

i would of expected $2^{102}$ to be the minimum power of 2 as 103 doesn't fit into any of the above cases but $2^{51}$ is the actual order.

  • 2
    In case anyone else is wondering: The question appears to be using the term "perfect shuffle" to refer to a shuffle similar to the [Faro shuffle](http://en.wikipedia.org/wiki/Perfect_shuffle), but with the even-numbered cards preceding the odd-numbered cards. @Ben: It would have been a good idea to explain what you mean by "perfect shuffle" in the question.2012-06-21
  • 0
    @joriki Especially since the answer is different if the shuffle results in the odd-numbered cards preceding the odd-numbered ones.2012-06-21

1 Answers 1