Author 
Topic: NEW PROBLEM: Shuffling cards into order (Read 4410 times) 

S. Owen
Full Member
Gender:
Posts: 221


NEW PROBLEM: Shuffling cards into order
« on: Sep 22^{nd}, 2002, 10:25am » 
Quote Modify

You have a deck of 52 cards  for convenience, number them 1 through 52. You cut the cards into two equal halves and shuffle them perfectly. That is, the cards were in the order 1,2,3,...,52 and now they are 1,27,2,28,...,26,52. If you repeat this shuffling process, will the cards ever return to their initial ordering? If so, how many shuffles will it take? How does the solution change if you have a deck of 64 cards, or 10, or in general, n cards? For odd n, shuffling will take 1,2,3,...,n to 1,(n+3)/2,2,(n+5)/2,...,n,(n+1)/2. For example, when n=5, the first shuffle yields 1,4,2,5,3. (modified to add definition for odd n)

« Last Edit: Sep 22^{nd}, 2002, 3:42pm by S. Owen » 
IP Logged 



Pietro K.C.
Full Member
Gender:
Posts: 213


Re: NEW PROBLEM: Shuffling cards into order
« Reply #1 on: Sep 22^{nd}, 2002, 11:55am » 
Quote Modify

I tried one approach for a little while, which is the following: numbering the cards sequentially 1...52, define f(n) to be the new position of card n, after one shuffling. For instance, given the shuffle 1,2,...,51,52 > 1,27,...,26,52, we have f(1)=1, f(27)=2, f(26)=51 and f(52)=52. Evidently, the formula for f is: f(n) = 2n1 if n <= 26 f(n) = 2n52 if n > 26. So the question is whether there exists a number A such that f^{A}(n) = n for all n (f^{A} = f iterated A times). This question is simpler than it appears at first. Suppose that there exists a number M such that f^{ M}(n) = n for ONE particular n. Then we must have f^{ 2M}(n) = f^{ 3M}(n) = ... = n, because f^{ kM}(n) = f^{ M}(f^{ M}(...f^{ M}(n))) (k times) for all k and n. From this property it follows that, if there are two numbers A and B, such that for distinct numbers n_{1}, n_{2} it holds that f^{A}(n_{1}) = n_{1} and f^{ B}(n_{2}) = n_{2}, then the least common multiple of A and B (lcm(A,B) = C) must satisfy f^{ C}(n_{1}) = n_{1} and f^{ C}(n_{2}) = n_{2}. This can be obviously generalized for all the cards; if to each card k corresponds a number A_{k} such that f^{Ak}(k) = k, then the number L=lcm(A_{1}, ..., A_{n}) satisfies the requirement f^{ L}(k) = k for all k. Furthermore, if each A_{k} is the least number that meets the respective condition, then L will be the least number that meets them all. This approach will lead us to the discovery of the number of shuffles necessary for the original configuration to return; but it appears to me that it will involve a lot of calculating (or maybe I'm just not being clever enough). So I turned to this other method, which guarantees that, for any deck of n cards, the cards WILL return to their original positions, though only God knows when. Suppose the cards do NOT go back to their original ordering. Then, since the number of possible orderings is finite (equal to n!), it must eventually reach an ordering in which it has been before. Call that O_{1}, and call O_{2}, ..., O_{m} the orderings in which the deck has been between the two consecutive occurrences of O_{1}. We assume that every O_{k} is distinct from the original ordering, O_{0}. After O_{1} is reached again, the deck will forever remain in this cycle of orderings: O_{1}, O_{2}, ..., O_{m}, O_{1}, ... Now we notice that, given an ordering O_{k}, the previous one, O_{k1}, is uniquely determined: we take every second card in the deck and place them in the bottom, ordered as before (call this "unshuffling"). This means that two different orderings, when shuffled, will remain different. Now consider the consecutive unshuffling of O_{1}; by hypothesis, we must have the following series of orderings: O_{1}, O_{m}, ..., O_{2}, O_{1}, ... This is a contradiction, because it implies that O_{0} will never be reached by the unshuffling process. However, unshuffle(shuffle(O)) = O for all orderings O; hence, given a sufficient number of unshufflings, we should return to the initial configuration. We conclude that no cycle can exist that does not include O_{0}, and we know that there MUST be a cycle; therefore O_{0} is reached again eventually. The best estimation of the number of shufflings required to restore the deck to O_{0} I can give, without further calculations, is (n2)!. This is because the first and the last cards are never moved from their places, and, in the worst case, all possible orderings of the intermediate cards will occur.

« Last Edit: Sep 22^{nd}, 2002, 11:59am by Pietro K.C. » 
IP Logged 
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was  the meaning of life. It was not what I expected." (Dogbert)



S. Owen
Full Member
Gender:
Posts: 221


Re: NEW PROBLEM: Shuffling cards into order
« Reply #2 on: Sep 22^{nd}, 2002, 3:50pm » 
Quote Modify

Yeah, the cards will always go back to their original ordering eventually. This surprised me when I first heard it, but it can be easily demonstrated, as in your argument. I don't know the general answer to this, but I do know the answer for n=52. You can find the solution manually with a deck of cards  it doesn't take that long, surprisingly! Pietro  I think your argument about finding L is exactly right. The extension of this idea is to look at the lengths of cycles of numbers here... that's as far as I've gotten though.


IP Logged 



TimMann
Senior Riddler
Gender:
Posts: 330


Hint + answer
« Reply #3 on: Sep 22^{nd}, 2002, 7:42pm » 
Quote Modify

Big hint for the 52card case: "Lengths of cycles of numbers" is the right kind of idea. The shuffle function f(n) is a permutation. One of the standard things to do with permutations is to factor them into cycles. For the 52card case, factoring f(n) into cycles gives: (1)(2 3 5 9 17 33 14 27)(4 7 13 25 49 46 40 28)(6 11 21 41 30 8 15 29)(10 19 37 22 43 34 16 31)(18 35)(52). The (1) means that 1>1; it's a cycle of length 1. The next sequence of numbers in parentheses says that 2>3, 3>5, 5>9, ... 27> 2. Etc. The representation as cycles is unique up to cyclically permuting the numbers in a cycle or reordering the set of cycles. You can quickly generate this representation from the definition of f(n); it's not really a lot of calculation. Simply compute (1 f(1) f(f(1)) ... ) until you get back to 1, then start again with the next number that's not already in a cycle, and keep repeating until all numbers are in cycles. The time and space required are O(N), where N is the number of cards. Total spoiler for 52 cards: Looking at f(n)'s factorization into cycles, since the cycle lengths are 1, 8, 8, 8, 8, 2, 1 it's obvious that if you apply f(n) eight times, each cycle will come back to where it started, but not if you apply f(n) fewer times. So the answer to the n=52 case is 8. More on other deck sizes. I don't know if there's a simple formula, but... To get the answer for any other deck size, you can follow the same procedure. Write the shuffle as a permutation, then factor it into cycles. The least common multiple of the lengths of the cycles is the answer.

« Last Edit: Sep 22^{nd}, 2002, 7:50pm by TimMann » 
IP Logged 
http://timmann.org/



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Shuffling cards into order
« Reply #4 on: Sep 24^{th}, 2002, 8:04am » 
Quote Modify

I suggested this problem to Will a while ago, but it managed to fall by the wayside. You should also try the "other" case (they're actually "equally" likely!) where f(1,2,3,...) = 27,1,28,... rather than 1,27,2,... Happy Puzzling, Eric


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



TimMann
Senior Riddler
Gender:
Posts: 330


Re: NEW PROBLEM: Shuffling cards into order
« Reply #5 on: Sep 24^{th}, 2002, 8:22am » 
Quote Modify

As I recall, Martin Gardner gives the bare answers for both the 1,26,... and the 26,1,... shuffles (that is, just the number of shuffles needed to return to the starting configuration, with no explanation of why) in one of his columns. The first time I read that column was probably more than 30 years ago when I was in grade school. It was fun after all this time to see the problem again and realize that the group theory class I'd taken in college 20 years ago gave me the tools to solve it. I remembered that the 26,1,... shuffle has quite a different answer, but didn't mention that in my post for some reason, I guess because I hadn't gotten around to writing out the cycles for that one. p.s. Gardner also mentioned that some magicians have trained themselves to do perfect riffle shuffles of this type and use them in tricks. Gamblers have also been known to use them to cheat! Of course, the person shuffling can control whether he does the 1,26... or 26,1... variant. I suppose I should go find that column and reread it now.

« Last Edit: Sep 24^{th}, 2002, 8:28am by TimMann » 
IP Logged 
http://timmann.org/



Pietro K.C.
Full Member
Gender:
Posts: 213


Re: NEW PROBLEM: Shuffling cards into order
« Reply #6 on: Sep 24^{th}, 2002, 12:12pm » 
Quote Modify

Yeah, the permutation thing is the easiest way to go, but at the time multiplying by 2 and subtracting 1 a bunch of times seemed like a lot of work! Anyways, I've come up with a way to give a rough approximation of the number of shuffles necessary (the number L such that f^{ L}(x)=x for all x in a bijection between an nelement set and itself), an approximation better than my previous (n2)!. It goes like this. If S has n elements and f : S > S is bijective, then for each x in S there exists a positive number A_{i} less than or equal to n with the property that f^{ Ai}(x) = x. This is a simple application of the platypushole principle (why all this biasing towards pigeons?). Hence, we are looking for L = lcm(A_{1}, ..., A_{n}) where A_{i} <= n for all i. Let p_{i} be the ith smallest prime less than n. Then the number u_{i}=floor( ln(n) / ln(p_{i}) ) is the largest power of p_{i} that will be less than n. In the worst case, we can imagine that, for each such power, there will be a cycle with length p_{i}^{ui}. Therefore, L <= product(p_{i}^{ui}), p_{i} <= n. For n=52, for instance, an estimate of the number of shuffles would be 32*27*25*49*11*13*17*19*23*29*31*37*41*43*47 = 3.099 x 10^{21}. Not very good, but better than 50! = 3.041 x 10^{64} nonetheless. I like this problem. It gives rise to interesting mathematics. I want to find a good upper bound L now, for general n. I suppose the prime power approach is a bit silly, because it doesn't consider that the sum of the factors must be equal to n itself. I suppose the real problem is: Given n, find numbers a_{1}, ..., a_{k} such that a_{1} + ... + a_{k} = n and their least common multiple is maximum. Now this problem seems hard. Maybe I'll post it separately in the Putnam section.


IP Logged 
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was  the meaning of life. It was not what I expected." (Dogbert)



TimMann
Senior Riddler
Gender:
Posts: 330


Re: NEW PROBLEM: Shuffling cards into order
« Reply #7 on: Sep 24^{th}, 2002, 10:22pm » 
Quote Modify

I looked up the Martin Gardner column. It's chapter 10 of Mathematical Carnival (Knopf, 1975). There's a great deal more information there than I remembered. Lots of spoilers, actually. Gardner gives a set of fairly simple formulas for the number of perfect riffle shuffles (or as he tells us American magicians call it, the faro shuffle) required to return a deck of size n to its initial order. The formulas are somewhat simpler than the method I described that involves factoring the permutation into cycles, so I'd encourage Pietro and others to keep thinking about the problem. Gardner doesn't give a proof, so I suppose I could still work on a proof even though I've had the partial spoiler of seeing the actual formulas. Gardner does describe the method I gave (though without introducing the standard notation and terminology) when discussing the problem of how many applications of an arbitrary permutation would be needed to return a deck to the original order. He also has a lot of interesting little tidbits in the column about shuffles and magic tricks that use them, and lots of followup puzzles. It's a fun read. Pietro, you should really read up on some group theory; you've already rediscovered some of the basics of it. I think that having done that will increase your enjoyment once you start reading about the standard treatment.


IP Logged 
http://timmann.org/



Chronos
Full Member
Gender:
Posts: 288


Re: NEW PROBLEM: Shuffling cards into order
« Reply #8 on: Sep 25^{th}, 2002, 8:51pm » 
Quote Modify

I once did the case of outshuffles of a 52 card deck by hand (an outshuffle is the 27,1,28,2... case. The 1,27,2,28... is an inshuffle. An outshuffle on n cards is equivalent to an inshuffle on n+2). I found that 13 outshuffles reversed the order, and another 13 returned it to the original. Perhaps this is the origin of the old canard that 7 shuffles gets you to maximum randomness? I also find it interesting that 13 is a factor of 52, but I'm not sure what the significance of that is.


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: NEW PROBLEM: Shuffling cards into order
« Reply #9 on: Sep 30^{th}, 2002, 11:09am » 
Quote Modify

Since the outshuffle is the basic function here, I was thinking about how many outshuffles it will take for a given number of cards. We only need to consider even numbers, because a "frontshuffle" or "backshuffle" on an odd number of cards is equivalent to an outshuffle on the first (or last) n1 of them. Here I catalog the various cyclesizes for smaller sets of cards. The first cycle listed is for the first card in the stack, and the others are listed in decreasing order. # cards, cycle sizes 0: 1 2: 2 4: 4 6: 3, 3 8: 6, 2 10: 10 12: 12 14: 4, 4, 4, 2 16: 8, 8 18: 18 20: 6, 6, 3, 3, 2 22: 11, 11 24: 20, 4 26: 18, 6, 2 28: 28 30: 5, 5, 5, 5, 5, 5 32: 10, 10, 10, 2 34: 12, 12, 4, 3, 3 ... 62: 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2 ... I'm sure this has to do with prime numbers ... Notes: 1) when n+2 is a power of 2, the solution takes on an interesting form... 2) For n = 6k + 2, we get a single cycle of 2. 3) The odd cycles always come in pairs. 4) The size of the later cycles always seem to be divisors of the size of the first cycle. 5) I think that the largest number is always equal to the length of the repeating part of 1/(n+1) written in base 2.


IP Logged 
Doc, I'm addicted to advice! What should I do?



