Author |
Topic: Messing with coin stacks (Read 1317 times) |
|
Deedlit
Senior Riddler
Posts: 476
|
 |
Messing with coin stacks
« on: Dec 18th, 2005, 5:14am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
|
Re: Messing with coin stacks
« Reply #1 on: Dec 18th, 2005, 6:31am » |
Quote Modify
|
n(n+1)/2 coins distributed in stacks of heights (n, n-1, n-2, n-3, .. , 2, 1) is stationary under the operation described above. To proof that any configuration converges to this distribution is another matter...
|
| « Last Edit: Dec 18th, 2005, 6:37am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Messing with coin stacks
« Reply #2 on: Dec 18th, 2005, 7:07am » |
Quote Modify
|
on Dec 18th, 2005, 6:31am, JocK wrote: To proof that any configuration converges to this distribution is another matter...
|
|
Let's see:
if we defne the entropy function S = number of distict stack heights, then one can show that:
1) S never decreases under the operation
2) the above described stationary distribution maximises S (for given n)
| hidden: |
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).
|
|
| « Last Edit: Dec 18th, 2005, 7:10am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Messing with coin stacks
« Reply #3 on: Dec 18th, 2005, 7:18am » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Messing with coin stacks
« Reply #4 on: Dec 18th, 2005, 7:31am » |
Quote Modify
|
on Dec 18th, 2005, 7:18am, 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... 
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Messing with coin stacks
« Reply #5 on: Dec 18th, 2005, 7:36am » |
Quote Modify
|
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.
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Messing with coin stacks
« Reply #6 on: Dec 18th, 2005, 7:37am » |
Quote Modify
|
Err... right. Try 4, 1, and 1. 
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Messing with coin stacks
« Reply #7 on: Dec 18th, 2005, 10:04am » |
Quote Modify
|
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'.
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Joe Fendel
Junior Member
Posts: 68
|
|
Re: Messing with coin stacks
« Reply #8 on: Dec 19th, 2005, 5:48pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print