Shuffling poker chips

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?

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

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.

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:

if x = 2, then the answer is 0.

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

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.

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

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...

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.

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).