posted 12 years ago

This problem was posed a while ago, and for anyone who cares I think I found the answer. I just don't want other people to live their lives in the frustration I have for the past couple months! The original problem was this:

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?

Now I believe the solution is this:

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

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?

Now I believe the solution is this:

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

james mulhern

Greenhorn

Posts: 3

posted 12 years ago

no problem. we'll see about deleting this thread then..

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