[High School - Calculus/Algebra/General Math] Card Shuffling Problem

[aTzUeLo1191]

Today our Calc teacher gave us a practice quiz for the upcoming year. On the quiz were a couple of trick problems that seemed hard but once you found out how to do them, they were much simpler. One of the problems, however, has given me a headache because I have been thinking throughout the day what the answer could be.

The question: if you shuffle a deck of cards perfectly starting with the left hand on top (meaning the first shuffle will be A,A,2,2,3,3,4,4 and so on), how many times will you have to shuffle it to return to its original position?

I did a few perfect shuffles, and I kept track of the 2nd card, the 2 of Spades. After a while, I noticed that the distance it travels throughout the deck keeps doubling - after 0 shuffles, its the 2nd card, after 1 shuffle its the 3rd card, after 2 shuffles, its the 5th card, and so on.

Now comes the tricky part. Because my numbers go past 52 and keep getting larger, its obviously not going to come back to the 2nd position. Will I know that the card has reached its original position when its place in the deck is a multiple of 52 plus 2 because its the 2nd card, or is it plus another number? Or, is my math totally wrong and I need to start from scratch? Please, any help (without giving me the answer, I want to find it myself for future problems) would be much appreciated.

[Mr.Nothing]

There is no such thing as a "perfect shuffle."
Unless your teacher is dumb, it's a trick question.
There is no telling which card would fall on bottom first, so on.

EDIT: Unless you left out vital details, it's kind of impossible for us to answer.

[Tasselfoot]

you should start with a smaller number and look for a pattern, then scale it. at least, to me, that's the easiest method. i'm 100% sure there is a mathematical solution as well that would give the same result.

Like.. assume that you are shuffling chips at a poker table, instead of cards. Same deal though. if you have 6 chips, how many shuffles will it take to get the chips in the same order?

If you have a stack with 123456, you'll have:
1 shuffle: 142536
2 shuffles: 154326
3 shuffles: 135246
4 shuffles: 123456

now let's try with 4: 1234
1st shuffle: 1324
2nd shuffle: 1234

let's try with 8: 12345678
1st shuffle: 15263748
2nd shuffle: 13572468
3rd shuffle: 12345678

now 10: 123456789A
1st: 162738495A
2nd: 186429753A
3rd: 198765432A
4th: 159483726A
5th: 135792468A
6th: 123456789A

4:2, 6:4, 8:3, 10:6... i'm sure there is a pattern in there somewhere. maybe you need to do it further out or something though.


edit: i bet it has to do with odds/evens and how many are in each stack. you have 2 in each stack, it takes 2 times. you have 4 in each stack, it takes 3 times. you have 3 in each stack, it takes 4 times. you have 5 in each stack, it takes 6 times.

let's try with 6 in each stack (aka, 12)... 123456789ABC
1st: 1728394A5B6C
2nd: 147A258B369C
3rd: 184B73A6295C
4th: 1A8642B9753C
5th: 1BA98765432C
6th: 16B5A493827C
7th: 1963B852A74C
8th: 15926A37B48C
9th: 13579B2468AC
10th: 123456789ABC

ok... so 2:2, 3:4, 4:3, 5:6, 6:10. makes my theory not right. you're trying to find 26:x. meh. oh well. probably something dealing with powers of 2.

[aTzUeLo1191]

@Mr. Nothing: What I mean by a perfect shuffle is that the deck is split 26 each, and then each side is layered, meaning the first shuffle of an unshuffled deck would be A,A,2,2,3,3,4,4,5,5 and so on.

@Tass: I tried that, but after 12 it starts to become tedious.

Would my method work at all? I ask this because once we find the correct answer, we have to explain our methods, and it would be easier to explain my own method than someone else's.

[Tasselfoot]

just did a little research... the answer is 8. although that only works for a 52 card deck. if you play pinochle, which is 48 cards, it'll be different.

if you want to write it down on paper and try it out... it should only take 8 shuffles.


edit:

The number of outshuffles required to restore any pack of cards to its original order does obey a simple rule. The problem is that one of the variables in the rule cannot be known in advance. So the only way to work out the number of perfect shuffles needed to return a pack to its original order is to do them. There is an exception: when the number of cards in a pack is exactly equal to two raised to the power of a whole number (that is, if the pack has 4, 8, 16, or 32 cards, and so on). Then, the number of outshuffles is the same as the exponent: for a pack of four cards it takes two outshuffles, for a pack of 32 cards it takes five.

More generally, it turns out that the number of outshuffles needed to get a pack back to its starting point is the smallest power of two - call it x such that two raised to the power of x and then divided by a figure that is one less than the number of cards in the pack leaves a remainder of one. For example, in the case of 52 cards, the number of outshuffles needed is eight (2^8 equals 256, and 256 divided by 51 has a remainder of one). But for all pack sizes that are not powers of two, x cannot be calculated, and the number of outshuffles required to return the cards to their original order cannot be worked out.

ha! told you it had to do with powers of 2!

edit2: for a 48 card deck, you'd have to shuffle 23 times. 2^23 = 8388608, and 47 goes evenly into 8388607.

[UphoricSHD]

Wow! Good job tassle!

This stuff makes my brain hurt...
(guessing I won't be counting cards anytime soon)