wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Messing with coin stacks
        
(Message started by: Deedlit on Dec 18^th, 2005, 5:14am)

Title: Messing with coin stacks
Post by Deedlit on Dec 18^th, 2005, 5:14am

You have n(n+1)/2 coins, arranged in various stacks. You successively apply the following procedure: Take a coin from each stack and put them all in a new stack.

What eventually happens to the coin stacks?

Title: Re: Messing with coin stacks
Post by JocK on Dec 18^th, 2005, 6:31am

n(n+1)/2 coins distributed in stacks of heights [hide](n, n-1, n-2, n-3, .. , 2, 1) is stationary under the operation described above[/hide]. To proof that any configuration converges to this distribution is another matter...

Title: Re: Messing with coin stacks
Post by JocK on Dec 18^th, 2005, 7:07am

on 12/18/05 at 06:31:57, JocK wrote:

To proof that any configuration converges to this distribution is another matter...

Let's see:

if we defne the [hide]entropy function S = number of distict stack heights[/hide], then one can show that:

1) [hide]S never decreases under the operation[/hide]

2) [hide]the above described stationary distribution maximises S (for given n)[/hide]

[hideb]

Ad 1) The operation keeps distinct stacks distinct and forms a new stack.

If before the operation all stacks have height > 1, then no stacks disappear, whilst a new stack is formed. As a result, the number of distinct stack heights can not decrease.

If before the operation one or more of the stacks have height 1, one stack height disappears, but the newly formed stack is distinct from the others (why?) As a result, the number of distinct stack heights does not decrease.

Ad 2) Obvious (with n(n+1)/2 coins one can not create more than n distinct stack heights).

[/hideb]

Title: Re: Messing with coin stacks
Post by Deedlit on Dec 18^th, 2005, 7:18am

I'm afraid that's not quite true - if I have stacks of size 1, 3, and 4, I get stacks of size 2, 3, and 3. But keep trying!

Title: Re: Messing with coin stacks
Post by JocK on Dec 18^th, 2005, 7:31am

on 12/18/05 at 07:18:09, Deedlit wrote:

I'm afraid that's not quite true - if I have stacks of size 1, 3, and 4, I get stacks of size 2, 3, and 3. But keep trying!

Yes, but the sum of 1, 3 and 4 is not a triangular number... ???

Title: Re: Messing with coin stacks
Post by JocK on Dec 18^th, 2005, 7:36am

Still, the above 'proof' is certainly not rigorous, and actually contains two gaps:

1) I still have to demonstrate that if at least one of the stacks has height 1, the newly formed stack has a height different from the other stacks.

2) The above argument does not exclude 'limit cycles' of constant S. I'm not certain how to prove these don't exist (one needs to demonstrate that as long as the equilibrium stack distribution is not reached, one keeps encountering steps that increase S).

It's a nice problem.

Title: Re: Messing with coin stacks
Post by Deedlit on Dec 18^th, 2005, 7:37am

Err... right. Try 4, 1, and 1. :)

Title: Re: Messing with coin stacks
Post by JocK on Dec 18^th, 2005, 10:04am

Hmmm... clearly I've been jumping to conclusions.

Still, I believe defining an appropriate entropy function would be the right way to prove one always reaches the stable distribution.

I see two possible ways out:
1)we need to define an entirely different entropy function, or:
2) the above entropy function is non-decreasing in some 'average way'.

Title: Re: Messing with coin stacks
Post by Joe Fendel on Dec 19^th, 2005, 5:48pm

The dual problem might be easier:

Begin with stacks of coins from 1 up to n.

On any turn take any stack that has at least as many coins as the number of stacks - 1, and distribute the coins from that stack: 1 for each existing stack and then make stacks of 1 coin with all leftover coins.

Prove that any stack combination (adding to n(n+1)/2) is possible to acheive this way.

I have no solution... yet. :)