Shuffling poker chips

[Nick George]

I have stack of x/2 green poker chips, sitting on top of x/2 red poker chips. When I shuffle my stack of chips, I separate the chips into the top half and the bottom half. I then alternate laying down a chip from the left and then right stack. How many times must I shuffle my stack of x chips such that they return to their original formation of green on top, red on bottom?

[Tim West]

When you separate the big pile into two stacks, does the top pile go to the left or right stack? I'm sensing an off-by-one error
If top -> left, then for x=1 the answer is 2, if top -> right, the answer is 1.
--Tim

[Nick George]

Let's start it of with an easy base: how many shuffles until the chips resegregate, with all of the chips of one color together, regardless of which stack is on top, and which is on bottom.

[Nick George]

i forgot to mention: when one shuffles, one takes from the bottom of the stack, not the top. And now for a random, gratuitus smiley:

[fred rosenberger]

if x = 2, then the answer is 0.

[Tim West]

You could argue that the answer is zero for all x, but I think you have to assume there's at least one shuffle. I'd say the answer for x = 2 is 1 :-)
Meanwhile, I'm still tearing up bits of paper on my desk to use as poker chips :-/

--Tim

[fred rosenberger]

I took 4 quarters, and stacked them from top to bottom as H-H-T-T.

divided them into two stack, T-T and H-H.

I then stacked them back up by dropping the bottom quarter from each stack into a new pile, alternating stacks. I started with the right stack, or heads. i ended up with T-H-T-H.

again divided, putting the top to quarters to the right. i had two stacks with H on top, and T on bottom.

i restacked them as before, dropping the bottom quarter from each stack, alternating, starting on the right. i ended up with H-H-T-T.

so, two shuffled reversed the original order. i would therefor assume 4 shuffles would restore it back to where i started.

i then repeated with 6 quarters. here's the stacks after each divide and shuffle...

H-H-H-T-T-T (initial condition)
T-H-T-H-T-H 1st shuffle
H-T-T-H-H-T 2nd shuffle
H-H-H-T-T-T 3rd shuffle

and now 8 quarters
HHHHTTTT initial
THTHTHTH 1 shuffle
TTHHTTHH 2 shuffles
TTTTHHHH 3 shuffles

my boss just got to work, so now i have to stop my experiments.

[Mario Loweystro]

Hey everyone-
I made a program for this and figured it all out for all x up to 500. I don't see any pattern, and it's starting to bug me. Check out what I found at http://www.freewebs.com/sedatesnail . (Sorry, the program's not up yet, but the list is).

I'm new here, so I don't know if making a program is the "easy cop-out" answer... but it's all I've got.
-Mario

[fred rosenberger]

Mario,

Welcome!! IMHO, writing a program is not an "easy cop-out" answer. You're probably gonna get some funny looks around here since you say you wrote it in C++, and this IS the JAVA Ranch, but whatever!

your data is really interesting...

i especially find the places like

61 20
62 100
63 7

where adding 1 more chip makes such a drastic difference. i may have to think about this one some more...

[Mario Loweystro]

Hey... oh yeah, the "Java Ranch" hehe. Well I only know C++ so far- I took one course in it in high school. I'll be learning Java as I start college in a few days... I just found this site on a Google search.

One thing that might affect it is the factors of each number... for example, multiples of 7 tend to take very few shuffles. Even numbers tend to take more shuffles than odd numbers. There are probably a bunch of other patterns like this. What's interesting is when the patterns collide... for example, 7's take few shuffles but 2's take many... then 14 takes a whopping 28 shuffles.

Also, it seems that the highest number of shuffles it can possibly take is double the number of chips.

[james mulhern]

The equation to this problem is not a simple one, as you might have guessed if you've spent some time thinking about it, but I believe it looks as follows:

2^x = 1 [modulo(n-1)], (I prefer to think of it as 2^x-1 = 0[modulo(n-1)]

where n = the total # of chips (both stacks), and x = the number of shuffles required to return the system to its original position.

Let me give an example solution:

For a stack of 10 chips (5 in each pile), the total number of shuffles is again given as:

2^x = 1[modulo(10-1)], or 2^x-1 = 0[modulo 9]

Now this next step takes a little "guess and check." You need to figure out the lowest power of two (minus one) which will give an integar result when divided by nine:

2^5 = 32
32-1= 31
31/9 = 3.4444 (non-integar) - wrong solution

2^6 = 64
64-1 = 63
63/9 = 7 (integar) - solution

This means that number of shuffles required for two stacks of 5 chips to return to there original position is 6. This is the same result we get when we actually try shuffling the chips. Try it for other numbers- it works!

By the way- for odd numbers, just use the equation 2^x-1= 0[modulo(n)], which will give you the same result as the even number of chips immediately following (# of shuffles for 5 chips = # of shuffles for 6 chips).