Nick George

Ranch Hand

Posts: 815

posted 13 years ago

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?

I've heard it takes forever to grow a woman from the ground

Tim West

Ranch Hand

Posts: 539

Nick George

Ranch Hand

Posts: 815

Nick George

Ranch Hand

Posts: 815

Tim West

Ranch Hand

Posts: 539

posted 13 years ago

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.

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.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Mario Loweystro

Greenhorn

Posts: 2

posted 13 years ago

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

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

posted 13 years ago
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

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

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

Greenhorn

Posts: 2

posted 13 years ago

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.

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

Greenhorn

Posts: 3

posted 11 years ago

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

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