|
||
|
Title: NEW PROBLEM: Shuffling cards into order Post by S. Owen on Sep 22nd, 2002, 10:25am 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) |
||
|
Title: Re: NEW PROBLEM: Shuffling cards into order Post by Pietro K.C. on Sep 22nd, 2002, 11:55am 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) = 2n-1 if n <= 26 f(n) = 2n-52 if n > 26. So the question is whether there exists a number A such that fA(n) = n for all n (fA = 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 n1, n2 it holds that fA(n1) = n1 and f B(n2) = n2, then the least common multiple of A and B (lcm(A,B) = C) must satisfy f C(n1) = n1 and f C(n2) = n2. This can be obviously generalized for all the cards; if to each card k corresponds a number Ak such that fAk(k) = k, then the number L=lcm(A1, ..., An) satisfies the requirement f L(k) = k for all k. Furthermore, if each Ak 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 O1, and call O2, ..., Om the orderings in which the deck has been between the two consecutive occurrences of O1. We assume that every Ok is distinct from the original ordering, O0. After O1 is reached again, the deck will forever remain in this cycle of orderings: O1, O2, ..., Om, O1, ... Now we notice that, given an ordering Ok, the previous one, Ok-1, 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 O1; by hypothesis, we must have the following series of orderings: O1, Om, ..., O2, O1, ... This is a contradiction, because it implies that O0 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 O0, and we know that there MUST be a cycle; therefore O0 is reached again eventually. The best estimation of the number of shufflings required to restore the deck to O0 I can give, without further calculations, is (n-2)!. 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. |
||
|
Title: Re: NEW PROBLEM: Shuffling cards into order Post by S. Owen on Sep 22nd, 2002, 3:50pm 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. |
||
|
Title: Hint + answer Post by TimMann on Sep 22nd, 2002, 7:42pm Big hint for the 52-card 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 52-card 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. |
||
|
Title: Re: NEW PROBLEM: Shuffling cards into order Post by Eric Yeh on Sep 24th, 2002, 8:04am 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 |
||
|
Title: Re: NEW PROBLEM: Shuffling cards into order Post by TimMann on Sep 24th, 2002, 8:22am 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. |
||
|
Title: Re: NEW PROBLEM: Shuffling cards into order Post by Pietro K.C. on Sep 24th, 2002, 12:12pm 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 n-element set and itself), an approximation better than my previous (n-2)!. 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 Ai 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(A1, ..., An) where Ai <= n for all i. Let pi be the i-th smallest prime less than n. Then the number ui=floor( ln(n) / ln(pi) ) is the largest power of pi 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 piui. Therefore, L <= product(piui), pi <= 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 1021. Not very good, but better than 50! = 3.041 x 1064 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 a1, ..., ak such that a1 + ... + ak = n and their least common multiple is maximum. Now this problem seems hard. Maybe I'll post it separately in the Putnam section. |
||
|
Title: Re: NEW PROBLEM: Shuffling cards into order Post by TimMann on Sep 24th, 2002, 10:22pm 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. |
||
|
Title: Re: NEW PROBLEM: Shuffling cards into order Post by Chronos on Sep 25th, 2002, 8:51pm I once did the case of out-shuffles of a 52 card deck by hand (an out-shuffle is the 27,1,28,2... case. The 1,27,2,28... is an in-shuffle. An out-shuffle on n cards is equivalent to an in-shuffle on n+2). I found that 13 out-shuffles 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. |
||
|
Title: Re: NEW PROBLEM: Shuffling cards into order Post by James Fingas on Sep 30th, 2002, 11:09am Since the out-shuffle 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 "front-shuffle" or "back-shuffle" on an odd number of cards is equivalent to an out-shuffle on the first (or last) n-1 of them. Here I catalog the various cycle-sizes 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. |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |