Card Shuffle
Story: I remember that I used to believe that shuffling cards more makes the pack "more" randomized. It turns out that if I was perfect, I would have given serious advantage to my opponents. Lets see how. :)
Source: William Wu's Puzzle Page
Puzzle: A perfect in-shuffle of a deck of 52 cards is defined as follows. The deck cut in half followed by interleaving of the two piles. So if the cards were labeled 0, 1, 2, …, 51, the new sequence is 0, 26, 1, 27, 2, 28, … With repeated in-shuffles, shall we ever get back the original order? In how many iterations? The shuffling technique described in the puzzle is known as the Faro Shuffle.
Update(12/01/10): On a related note, I was searching for optimal shuffling algorithms and found this an interesting read.
Update (14/01/10): Solution posted by me in comments!!
Source: William Wu's Puzzle Page
Puzzle: A perfect in-shuffle of a deck of 52 cards is defined as follows. The deck cut in half followed by interleaving of the two piles. So if the cards were labeled 0, 1, 2, …, 51, the new sequence is 0, 26, 1, 27, 2, 28, … With repeated in-shuffles, shall we ever get back the original order? In how many iterations? The shuffling technique described in the puzzle is known as the Faro Shuffle.
Update(12/01/10): On a related note, I was searching for optimal shuffling algorithms and found this an interesting read.
Update (14/01/10): Solution posted by me in comments!!
Cards are numbered from 0 to 51.
ReplyDeleteLet us trace the position of card numbered 1.By the time it reaches position number 26, one more shuffle will result in original order tht we started with.
When it is in left half, its position get doubled with a shuffle.
When in second half, say in position POS, then after one more shuffle it will be in (2*POS)-51 position.
Using these, the following are the positions of card 1 after each shuffle :
1, 2, 4, 8, 16, 32, 13, 26, 1
Thus after 8 perfect shuffles, we get original order.
@Pratik : Is there a nice closed form formula for the number of shuffles required, given #of cards N ?
easy special case is if N is a power of 2, then Log N is the number of perfect shuffles required.
@Giridhar.. Card 1 would reach its place in 8 shuffles. What about other cards? We want all the cards to reach their place back.
ReplyDeleteits trivial that cards will come to original position after some N as number of permutation is limited.
ReplyDeleteI think minimum number of shuffling required is 24.
here is why I think so (not rigorously verified though)
each card's position after a shuffle is 2n mod(52),so after k shuffle it will be 2^k*n mod 52,so we must have 2^k=1 mod 52,so k is given by phi(52)=(13-1)*2=24 ...isn't it the required thing?
small correction- correct answer is 8.
ReplyDeleteposition after k shuffle would be 2^k*n mod 51 so smaalest number would be 2^k = 1 mod 51 and
(2^8) mod 51 = 1 can be easily seen.
@Piyush..
ReplyDeleteAnswer 8 is correct but the solution is not..
BTW, why mod 51? In any case, not all the cards follow this simple pattern as you have shown.
Here is the solution:
Any shuffle is a permutation. Let the cycle lengths of the permutation be c1, c2, c3, .. Then the number of iterations is the LCM of c1, c2, c3, ..
With 52 cards, let the cards be labeled 0, 1, 2, .. 51. Then cutting and interleaving results in 0, 26, 1, 27, 2, 28, .. , which is equivalent to the following “moves”: { 0 -> 0, 1 -> 2, 2 -> 4, 3 -> 6, 4 -> 8, ... , 26 -> 1, 27 -> 3, 28 -> 5, 29 -> 7, … 51 -> 51}.
The inverse of these moves can be captured succinctly as follows: If i is even, i –> i/2. If i is odd, then i -> 26 + (i-1)/2. The formula helps us to list cycles of the permutation in reverse order:
(length 1) 0 -> 0
(length 1) 51 -> 51
(length 8) 50 -> 25 -> 38 -> 19 -> 35 -> 43 -> 47 -> 49 -> 50
(length 8) 48 -> 24 -> 12 -> 6 -> 3 -> 27 -> 39 -> 45 -> 48
(length 8) 46 -> 23 -> 37 -> 44 -> 22 -> 11 -> 31 -> 41 -> 46
(length 8) 42 -> 21 -> 36 -> 18 -> 9 -> 30 -> 15 -> 33 -> 42
(length 8) 40 -> 20 -> 10 -> 5 -> 28 -> 14 -> 7 -> 29 -> 40
(length 2) 34 -> 17 -> 34
(length 8) 32 -> 16 -> 8 -> 4 -> 2 -> 1 -> 26 -> 13 -> 32
So the answer is LCM of {1, 2, 8}, which is 8 shuffles!
So, in 8 shuffles, I will get my initial permutation of cards back.
my solution is correct!
ReplyDeleteevery number follows that rule of multiplication of 2, leave 51 and 0 because they always remain at the same position,now see 1 goes to 2 and so on similarily 26 goes to 2*26=52 =1 mod 51,so other number also follow that rule!
Now instead of multiplication factor as 2 you can take any number relativly prime to 51(say 5) and try the same shuffling algo.
and see the number of shuffle to restore original shuffle and if you amaze to see the answer is each time a power of 2,then think why is it so.
Alternatively to prove me wrong give me multiplication factor such that number of shuffle required is not any number other then power of two or otherwise if you wish.
bottomline is to solve this each time you have to find solution of modular equation 2^x=1 mod n;
here n = number of cards minus one and x is number of shuffle required. you can also try this with other n like 7,9 11 etc.
http://www.wolframalpha.com/input/?i=2^8*{0%2C1%2C2%2C3..51}+mod51
Somehow the numbers seem to match.
ReplyDeleteTwo doubts:
1) Why is it not capturing the state of card numbered 51. why only 0...50?
2) How did you come up with this? Why is mod 51 giving the correct answer? Did you come up with this studying the patterns?
it doesn't matter for 51. as it is already 0 mod 51 and will remain forever there.
ReplyDeletemy proof is very basic group theory.how can cryptologist miss this easy thing .!
a little search on faro search I found this document which gives the same proof as mine.
www-stat.stanford.edu%2F~cgates%2FPERSI%2Fpapers%2F83_05_shuffles.pdf
page 3 (177)
www-stat.stanford.edu/~cgates/PERSI/papers/83_05_shuffles.pdf
ReplyDelete:) Thanx a lot!!
ReplyDelete