aspose file tools*
The moose likes Programming Diversions and the fly likes Shuffling poker chips Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Shuffling poker chips" Watch "Shuffling poker chips" New topic
Author

Shuffling poker chips

Nick George
Ranch Hand

Joined: Apr 04, 2004
Posts: 815
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

Joined: Mar 15, 2004
Posts: 539
When you separate the big pile into two stacks, does the top pile go to the left or right stack? I'm sensing an off-by-one error
If top -> left, then for x=1 the answer is 2, if top -> right, the answer is 1.
--Tim
Nick George
Ranch Hand

Joined: Apr 04, 2004
Posts: 815
Let's start it of with an easy base: how many shuffles until the chips resegregate, with all of the chips of one color together, regardless of which stack is on top, and which is on bottom.
Nick George
Ranch Hand

Joined: Apr 04, 2004
Posts: 815
i forgot to mention: when one shuffles, one takes from the bottom of the stack, not the top. And now for a random, gratuitus smiley:
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11314
    
  16

if x = 2, then the answer is 0.


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

Joined: Mar 15, 2004
Posts: 539
You could argue that the answer is zero for all x, but I think you have to assume there's at least one shuffle. I'd say the answer for x = 2 is 1 :-)
Meanwhile, I'm still tearing up bits of paper on my desk to use as poker chips :-/

--Tim
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11314
    
  16

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.
Mario Loweystro
Greenhorn

Joined: Aug 19, 2004
Posts: 2
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
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11314
    
  16

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...
Mario Loweystro
Greenhorn

Joined: Aug 19, 2004
Posts: 2
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.
james mulhern
Greenhorn

Joined: Dec 27, 2005
Posts: 3
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 agree. Here's the link: http://aspose.com/file-tools
 
subject: Shuffling poker chips