Win a copy of Bad Programming Practices 101 (e-book) this week in the Beginning Java forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Poker chips shuffling 2

Greenhorn
Posts: 3
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).

james mulhern
Greenhorn
Posts: 3
Sorry I didn't know how this site works- didn't mean to post this twice. My bad.

lowercase baba
Bartender
Posts: 12626
50