Chip shuffling puzzle...

[mizuchaud]

Here's a puzzle for everyone.
Try to figure it out in your head before you physically try it.

Just noticed it while shuffling two different colors of chips together.

If you had two stacks of five chips, (total of ten chips), say a red stack on your left and a black stack on your right, how many PERFECT shuffles does it take to retrun the stacks to sorted colors: red on one side and black on the other?

How many shuffles would it take to resort two stacks of six?

Two stacks of seven?

Two stacks of eight?

And the last question: how many shuffles would it take to resort two stacks of four?

Post your answers. Then try it. (For the shuffle-impaired, do it manually.) Then someone post a mathematical reason for it.
(I don't know it, I've just noticed the pattern)

Have fun! If anything, it's great practice for perfect shuffling.

[jdunford]

Originally Posted by mizuchaud

Here's a puzzle for everyone.
Try to figure it out in your head before you physically try it.

Just noticed it while shuffling two different colors of chips together.

If you had two stacks of five chips, (total of ten chips), say a red stack on your left and a black stack on your right, how many PERFECT shuffles does it take to retrun the stacks to sorted colors: red on one side and black on the other?

How many shuffles would it take to resort two stacks of six?

Two stacks of seven?

Two stacks of eight?

And the last question: how many shuffles would it take to resort two stacks of four?

Post your answers. Then try it. (For the shuffle-impaired, do it manually.) Then someone post a mathematical reason for it.
(I don't know it, I've just noticed the pattern)

Have fun! If anything, it's great practice for perfect shuffling.

I think the rule is:
for 2n chips (shuffling two stacks of n chips each), it takes
* n-1 if n is even
* n+1 if n is odd

I'll check this first, then if I'm write I'll give you the proof.

* EDIT * Nope... trying again.

Depends if n = 2^m for integer m. In that (simplest) case, it takes m+1. I'm working on the other cases.

[99%evil]

Do the stacks of 8 chips have to go back in the same order you started? Cuz this will muck things up

[Gagne]

I think he just means all 1 color in any order on one side and the other color on the other side, Im not good with math, so I wont even try

[99%evil]

Originally Posted by Gagne

I think he just means all 1 color in any order on one side and the other color on the other side, Im not good with math, so I wont even try

They are the same color, but not in the original oreder...just getting the specifics

[jdunford]

Well, I've worked out the following:

n - bin - shuffles - bin
1 - 0001 - 1 - 0001
2 - 0010 - 2 - 0010
3 - 0011 - 4 - 0100
4 - 0100 - 3 - 0011
5 - 0101 - 6 - 0110
6 - 0110 - 10 - 1010
7 - 0111 - 12 - 1100
8 - 1000 - 4 - 0100
9 - 1001 - 8 - 1000
10 - 1010 - 18 - 10100

(bin just means the binary form of the previous number... 'cause it's really a binary problem)
I'm certain that stacks of size 2^m require m+1 shuffles to return to their original state. As for 2^m + k, I'm not certain I've got it yet.
The only patterns I see beyond that are:
- for 2^m+1, it takes 2*(m+1)
- for everything else, it takes 2*(n-1)
but I'm not sure how long it obeys that trend.

[mizuchaud]

Well, my original question was how many shuffles would it take to get two single color stacks.

I think 99's asking the question if I mean " back to their original poisitions": ie. red on the left and black on the right. I'm just interested in the original question as posed.

Just by doing shuffles and not MATH (yikes) I get an interesting number of shuffles for multiples of 4 chips in stacks (4 and 8 chips in the stacks) to attain single color stacks.

SPOILER BELOW..

I get three shuffles to reattain single colors for a 3 chip stack.

Three shuffles to achieve single colors for a 4 chip stack, but in the wrong positions.

Five shuffles for five chip stacks, but wrong position.

Six shuffles for 6 chips, with wrong positions.

7 for 7

but the kicker is that I get FOUR shuffles for an eight chip stack.

In my primitive head I latched onto the multiples of four as a subset of shuffling numbers.
junford, can you state that as a solution?


I'm hurting my head trying to figure out jdunford's phrasing.
what's the ^ mean?

[jdunford]

Originally Posted by mizuchaud

Well, my original question was how many shuffles would it take to get two single color stacks.

I think 99's asking the question if I mean " back to their original poisitions": ie. red on the left and black on the right. I'm just interested in the original question as posed.

Just by doing shuffles and not MATH (yikes) I get an interesting number of shuffles for multiples of 4 chips in stacks (4 and 8 chips in the stacks) to attain single color stacks.

SPOILER BELOW..

I get three shuffles to reattain single colors for a 3 chip stack.

Three shuffles to achieve single colors for a 4 chip stack, but in the wrong positions.

Five shuffles for five chip stacks, but wrong position.

Six shuffles for 6 chips, with wrong positions.

7 for 7

but the kicker is that I get FOUR shuffles for an eight chip stack.

In my primitive head I latched onto the multiples of four as a subset of shuffling numbers.
junford, can you state that as a solution?

I think you have to be careful... Let's say you have red on the left and green on the right, after the first shuffle you'll have:
r-g-r-g-r-g-r-g-...
In order to keep the shuffling consistent (with "perfect shuffles"), you'll need to move the top half of this stack to the left (i.e. the left MUST start with a red). Otherwise, you're not shuffling the same way each time. You'll notice that, if you do it "correctly" (or at least the way I did), the top chip will always be the same (and always on the left). If you're starting with red on the left and green on the right, and end up with green on the left, you must have switched your pattern (or kept switching after each shuffle). Using "the top always becomes left", I got the table I posted above.

(Of course, if you shuffle the other way, just switch "left" with "right" in the previous paragraph and you'll get the same result).

Originally Posted by mizuchaud

I'm hurting my head trying to figure out jdunford's phrasing.
what's the ^ mean?

The ^ symbol means "exponent" (i.e. 2^m means "2 to the power of m").
1 = 2^0
2 = 2^1
3 = 2^1 +1
4 = 2^2
5 = 2^2 +1
6 = 2^2 +2
7 = 2^2 +3
8 = 2^3
...

You'll find that with 16 chips in each starting stack, it only takes 5 shuffles (if you can shuffle stacks that high). It's fairly easy on paper, but takes a long time for more than a few shuffles (e.g. it took me several minutes to work out stacks of 10... and knowing that 11 was going to take even longer, I decided to stop there).

In short, chips in stacks of 1, 2, 4, 8, 16, 32, 64, ... take very few shuffles (e.g. 1, 2, 3, 4, 5, 6, 7, ...). For everything else, it takes a lot more shuffles... and I still haven't figured out the general rule.

[mizuchaud]

Originally Posted by jdunford

I think you have to be careful... Let's say you have red on the left and green on the right, after the first shuffle you'll have:
r-g-r-g-r-g-r-g-...
In order to keep the shuffling consistent (with "perfect shuffles"), you'll need to move the top half of this stack to the left (i.e. the left MUST start with a red). Otherwise, you're not shuffling the same way each time. You'll notice that, if you do it "correctly" (or at least the way I did), the top chip will always be the same (and always on the left). If you're starting with red on the left and green on the right, and end up with green on the left, you must have switched your pattern (or kept switching after each shuffle). Using "the top always becomes left", I got the table I posted above.

(Of course, if you shuffle the other way, just switch "left" with "right" in the previous paragraph and you'll get the same result)..

That's an interesting point.
If I start with red on the left and green on the right, I get, from the felt up, g-r-g-r-g-r-g-r-g-r after the first shuffle. I then cut the stack and transfer the top half to the RIGHT. I did this consistently through the sequence and got what I posted (five shuffles for five chip stacks)
If I do it the way you state, which leaves the red on top always, I get what you get, six shuffles.

Is it because of the way the right stack starts as the first chip in the stack sequence? Am I building in a loop by cutting to the right?

[noelsarchs]

too much math, just do 5 shuffles and you are back to even.