my dog learned polymorphism
The moose likes Programming Diversions and the fly likes Poker chips shuffling 2 Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Reply locked New topic

Poker chips shuffling 2

james mulhern

Joined: Dec 27, 2005
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

Joined: Dec 27, 2005
Posts: 3
Sorry I didn't know how this site works- didn't mean to post this twice. My bad.
fred rosenberger
lowercase baba

Joined: Oct 02, 2003
Posts: 11952

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
I agree. Here's the link:
subject: Poker chips shuffling 2
It's not a secret anymore!