Solution to Problem 44

Congratulations to this week's winners

Felice Kelly and Ray Kremer

Correct solutions were also received from Nathan Pauli, and Bradley alumnus Brian Laughlin, as well as from Denis Borris, Philippe Fondanaiche, and Robert T. McQuaid. 

 After a little experimentation, you'll see that the card originally in the i 'th position will have moved to the position given by the function p(i) defined by

p(i) = {
2i - 1, for i between 1 and 26
2(i-26),  for i between 27 and 52
 
You can now follow along and see, for example, that card 1 returns to the first spot, while card 2 migrates in order through positions 2 - 3 - 5 - 9 - 17 - 33 - 14 - 27 and then returns to position 2.  The following table lists the movement of the cards.
 
1 - 1
2 - 3 - 5 - 9 - 17 - 33 - 14 - 27 - 2
4 - 7 - 13 - 25 - 49 - 46 - 40 - 28 - 4
6 - 11 - 21 - 41 - 30 - 8 - 15 - 29 - 6
10 - 19 - 37 - 22 - 43 - 34 - 16 - 31- 10
12 - 23 - 45 - 38 - 24 - 47 - 42 - 32 - 12
20 - 39 - 26 - 51 - 50 - 48 - 44 - 36 - 20
18 - 35 - 18
52 - 52

You can immediately conclude that the deck will return to its original state after only 8 shuffles.  Among the many curious patterns, notice how cards 18 and 35 flip positions after each shuffle.

The situation is much different for 54 cards; a similar analysis gives that
you'll need 52 shuffles in order to return the deck to its initial state.  Moreover, each card (other than the top or bottom card) will migrate through each of the other 52 positions of the deck!

For the general case, it becomes useful to renumber the deck of n cards from 0 to n-1.  The equation for the shuffle then becomes

p(i) = 2i (modulo n-1)

This gives that the number of shuffles is the order of the residue 2 in the group of units, under multiplication, modulo n-1, from which you can derive the following
table for the number of shuffles.
 
 
n 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50
number of  
shuffles		 2 4 3 6 10 12 4 8 18 6 11 20 18 28 5 10 12 36 12 20 14 12 23 21
 

You are visitor number  4210 to this page. Page last updated 17 October 1998.