math problem

[kpux]

I was at Foxwoods the other night, and instead of trying to have winning session, I was concentrating on chip shuffling. I was trying to figure out a formula for how many iterations it takes two stacks of n chips to get back to their original configuration, assuming you shuffle them perfectly, and the stack on the left always contributes the bottom chip to the shuffled stack.

My friend and I thought about this for a long time, and we thought the best answer had to do with permutation groups, but we are still unsure. Any clever insights?

[ACPlayer]

Martin Gardner in Sci. Am. I believe perhaps 25 years ago once presented the problem of the perfect shuffler. That is how many times do we need to shuffle a deck of cards to get the original configuration.

The answer was just 8. Surprised?

Incidentally there are two types of shuffles.

[eviljeff]

a friend of mine had a similar problem involving a deck of cards presented to him when applying for a job. he initially tried to brute force it, but soon realized it would take way too long and the whole point of the question was to find a slick method.

basically you can solve the problem by doing one shuffle iteration to find out how often each chip returns to its initial position. (i.e. chip 1 went to position 4, the chip that was there went to position 16, which went to position 7, which went... it takes X shuffles for chip 1 to come back to position 1). once you have the periods for each chip, find the least common multiple.

[kpux]

Yes, I am surprised. We also contemplated that if we could answer the chip shuffling question, we could do the same with a deck of cards. But really, just 8? Wa wa wee wa.

What are the two types of shuffles? I mean, shuffling with alternating chips from each stack must be the "standard" shuffle. I can't think of another one that would be useful in answering our problem. Not meaning to sound like a jackass or anything.

[kpux]

[ QUOTE ]
(i.e. chip 1 went to position 4, the chip that was there went to position 16, which went to position 7, which went... it takes X shuffles for chip 1 to come back to position 1). once you have the periods for each chip, find the least common multiple.

[/ QUOTE ]

Yeah, that's basically how we figured we could solve the problem. But is there any general formula that expresses the number of shuffles needed to return the chips to normal if we have n chips in each stack? I mean, in terms of n.

After doing some initial trials, my intuition led me to think that maybe there is a serparate formula for chip stacks that are powers of 2, or maybe chip stacks that are prime numbers, etc...

[daryn]

there was a thread on this a while back. if i remember correctly it gave the name "A-shuffle" to a shuffle that was perfect, i.e. started with the same chip on the bottom and each cheap in the same spot every time. it also gave the number of A-shuffles necessary to return a stack of a certain size to its original configuration. it did this for 4, 6, 8, 12 chips i think.

[daryn]

ha.. each "cheap"

for some reason i can't edit anymore

[Cooker]

I am attacking the problem in earnest. I have developed a way to do it fairly quickly involving permutations, but have yet to be able to generalize this method. If you express the shuffle as a permutation in cycle notation the least common multiple of the cycle lengths is the number of shuffles required. This is basically restating the period thing earlier, but provides a more systematic approach. Now I simply need a quick way to get the cycle lengths and I will be done.

Still note that while this method gives the number of shuffles to return to the exact starting configuration, if you start with 2 stacks of the same size and different colors, the colors may separate with much fewer shuffles (this seems like a much harder problem to me).

I just thought of something and may be close to a full solution which I will post later after I have flushed it out.

[aloiz]

This only works for in-shuffles (123456 -> 142536 -> 154326) with an even number of chips/cards.

Let n be the number of things shuffled and x be the number of in-shuffles necessary to return the deck to orginal order:
mod(2^x-1, n-1) = 0

aloiz

[aloiz]

I just realized that since an out-shuffle is just like an in-suffle with two extra cards the number of out-shuffles to return a deck to its original order would be mod(2^x-1,n+1) = 0

aloiz