I know that as one of the student mathematicians I should be answering questions, not asking them, but here is a fascinating little question that is giving me some difficulties. It's a well known result that if you "perfectly shuffle" a deck of 52 cards 8 times, you get back to the original order. I was wondering if this result is easily generalised to 2n cards. By a "perfect shuffle" I mean that if the cards are numbered 1,2,3,...,2n before the shuffle, then they are number 1,n+1,2,n+2,3,n+3,...,2n after the shuffle. I've already written a program which calculates the number for any given n, (very quickly too), but I'd be interested in finding a closed form solution in terms of n.

Hi Dan,

I think that if you have 2n cards then the answer you are looking for (call it x) is the smallest integer that satisfies:

2^x = 1 (mod 2n-1)

However, I can't find a way of reducing this further.

Yours,

Michael

Sounds plausible, and works for n=26, but how did you derive this result?

D'oh! OK, I've been being a bit thick, I agree with the above result. Does anyone know a way to find a neat closed form for this result?

Well, I was simply lucky enough to spot the pattern that if x_n gives the position in the pack (with the numbering starting at 0 going up to 2n-1) of a certain card after r shuffles then:

2x_r = x_r-1 (mod 2n-1)

which is very easy to prove once you've spotted it. From here the question becomes much easier. Was this the same method you used to verify the result?

The result generalises if you shuffle by splitting the deck of 3n into 3 piles and then alternate the cards from the three piles during the shuffle (I don't know anyone who can do this!) Now the requirement is:

3^x = 1 (mod 3n-1)

and this generalises upwards.

No luck with simplifying the requirement - it seems a bit too hard to work out the factors of 2^x -1.

Yours,

Michael

Yes, that's basically the method I used, but in a slightly more group theory-ish way, because I like to make things more difficult than they really are, d'oh! Well, I have a nice result if n is a power of 2. For future discussion on this topic, how about using S(n) to be the number of shuffles needed. My first result then is that:

S(2^k )=k+1

The reason for this is that 2^k < 2n-1=2^k+1 -1 and 2^k+1 =1 (mod 2^k+1 -1). I've written a program which calculates S(n) for any given n, the C++ code is as follows:


int shuffle(int n)
{
int m=2*n-1;
int x=2%m;
for(int k=1;;k++)
{
if(x==1) return k;
x = (2*x)%m;
}
return 0;
}


I've compiled this program, and you can download the program from my website .
[Unfortunately this link is now broken. - The Editor]

There's a lot of pattern in the series, which begs to be explained, here are the results for the first 30 n:

Hi.

You know I think that in fact what you described in your first message is really a type of "unshuffle". If the cards are numbered 1,2,3,...,2n before then they should be numbered 1,3,5,7,...,2n-1,2,4,6,8,...,2n afterwards. You gave the reverse of this, so it doesn't matter at all, as we are looking for x shuffles not to change anything.

Anyway, I can prove also that:

S(2^k +1) = 2(k+1)

First of all it is clear that 2(k+1) shuffles will return the pack to its original order (difference of two squares) and then by tracking the movement of the card initially numbered 2, it is also clear that this is the least number of shuffles (excluding 0) that will return the order. This also shows that the lowest multiple of 2^a +1 in the form 2^r -1 is 2^2a -1 - something I wouldn't be able to show otherwise.

By the way, if n = 2^k , then you can represent the position of a card (in the deck of 2^k+1 ) as follows:

first you say whether it is in the first or second half of the deck

within this half, is it in the first or second half?

within this half is it in the first or second half.

Represent "first" by 0 and "second" by 1 at each stage. So for example in a deck of 8 the position of the 4th card is:

011

whereas in a deck of 16 cards the first card is:

0000.

Now the interesting thing is that when you "shuffle" the deck, the number cycles. For instance with the 10th card in 32 it goes:

01001
10010
00101
01010
10100
01001

and so this is an alternative demonstration that 2^k cards take k shuffles.

Yours,

Michael

I've just discovered that there is no known closed form solution to this problem. However, that doesn't have to stop us finding out some interesting things about it. Also worth mentioning, it's quite easy to show that:

S(n) < = 2(n-1)

Well, I did manage to work out a proof of that but I wouldn't call it quite easy (for me anyway). Your assertion is equivalent to the statement

for every odd n there exists an integer x smaller than n such that 2^x -1 is a multiple of n.

So to show this I considered y(x) = 2^x -1 mod n.

So y(0) = 0, y(1) = 1, y(x) = 2y(x-1)+1 (mod n) which can be seen by expanding out 2^x -1 geometrically.

The good news is that the sequence y(x) is not only forward deterministic (if you know y(x-1) you know y(x)) but it is also backward deterministic. There is only one value (mod n) that satisfies y(x-1) in y(x) = 2y(x-1)+1 because n is odd.

So now if the sequence y(x) ends up oscillating then it must return to zero first. That is the only way. Any other way would break the backwards deterministic rule, as the sequence starts with zero.

Now there are only n values that y(x) mod n can take, so after the initial value of zero, it must hit zero again within n-1 values of y(x). Therefore a value of x exists smaller than n that satisfies the criteria, and so:

S(n)< 2n-1 as required.

Anyway, how did you do it, and even more puzzling, how did you guess the result?

So anyway so far we have:

S(2^k ) = k+1
S(2^k +1) = 2(k+1)
and
S(n)< =2(n-1)

Yours,

Michael

PS. How did you prove that S(x) cannot be written in closed form?

I didn't actually manage to prove S(n) cannot be written in closed form, but I've been told that the solution to this problem is not known. In fact, it is not even known if there are an infinite number of prime numbers p such that if n=(p+1)/2, then it takes p-1 shuffles to return to the original deck. I'm not certain of my source, so this might all be wrong.

Secondly, there is an easier way to prove the above result, using a bit of group theory. Because we know that S(n) is the order of 2 modulo 2n-1, i.e. the smallest integer k such that 2^k =1 (mod 2n-1). The multiplicative group F_2n-1 ^X has 2n-2 elements: 1,2,...,2n-2. So, the order of 2 modulo 2n-1 must be less than or equal to the size of the group, 2n-2. i.e. S(n)< =2(n-1).

I guessed the result while I was playing around with some group theory stuff with it, and it is obvious if you plot the graph of S(n) against n. Here is another bound:

S(n)> =1+log₂ (n)

this is easy to derive because 2^k > =2n for 2^k =1 (mod 2n-1). Take logs to base 2 and you get the result.

Another bound that someone else came up with is that for n=3k+2 for some k, S(n)< =2(n-2). This is because cards (2k+1) and (4k+2) swap places in each shuffle and so are seperate from the rest of the pack. I know that isn't a proof, but it sort of works if you think about it.

Well, I didn't really understand the group theory proof but this is because I only know the very very basics of the subject. I should be able to find more about it soon, so I'll have another look at the proof then. I've just discovered a gap in my argument above. I said that each time you double the number and add one (going from y(n) to y(n+1)) then there are only n values that y(n) mod n can take, and so 0 must be hit within n-1 jumps. In fact this argument suggests that it must be hit within n jumps not n-1. To prove it is in fact n-1 we use the fact that y(n) can never be n-1 (mod n). This can be proven by induction (if y(n)=n-1 (mod n) then y(n-1) = n-1 (mod n) because n is odd, therefore y(n) =/= n-1 (mod n)).

Anyway, I can't seem to spot any more patterns in S(n). I wonder if the function S(n) hits all the integers...?

Yours,

Michael

Well of course it does, as S(2^k ) = k+1! Sorry.

Going back to what you were saying about it being unknown whether there are an infinite number of primes, s.t. if n = (p+1)/2 then p-1 shuffles are required. I've just realised that Fermat's Little Theorem (which was being discussed on another page) shows that p-1 shuffles will do the trick, but of course you may be able to do it in fewer. Which sources have you got information from on this question?

Thanks,

Michael

The source is someone on sci.math which is a maths discussion group (usenet) on the internet. You might be able to access it by clicking on this link: news:sci.math , otherwise try using www.deja.com and going to sci.math.