## Coins and Scales ... but not what you think.

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Mountainhawk
Posts: 199
Joined: Tue Aug 19, 2008 11:23 pm UTC
Location: Salem, MA

### Coins and Scales ... but not what you think.

Here is a puzzle I'm taking from a magazine I get. I thought I intuitively knew the answer, and I did, but I can't prove it and the solution given in this months issue does a magic hand wave over the part I can't prove.

There is a setup with a coin slot that leads to a pair of balance scales. The arms of the scales are slanted so the coin may fall into a bucket on the left or a bucket on the right. The probability of the coin rolling into a bucket is proportional to the number of coins already in the bucket. (That is, if the left bucket has 13 and the right bucket has 4, the probability of the 18th coin falling into the left bucket is 13/17).

We seed each bucket with 1 penny, so the first coin doesn't determine the result of all the other coins. We take 998 other pennies, and put them 1 by 1 into the coin slot, allowing them to fall into a bucket.

What is the expected value of the money in the lighter bucket when this process is finished?
"It doesn't matter who you vote for, the government always gets in." -- Elizabeth May, Canadian Green Party Leader

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

### Re: Coins and Scales ... but not what you think.

The puzzle is not well-defined. In the case where you wind up with 500 pennies and 500 pennies, do we arbitrarily decide that one is the lighter side, do we say there is no lighter side, or do we declare both sides to be the lighter side?
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

Mountainhawk
Posts: 199
Joined: Tue Aug 19, 2008 11:23 pm UTC
Location: Salem, MA

### Re: Coins and Scales ... but not what you think.

btilly wrote:The puzzle is not well-defined. In the case where you wind up with 500 pennies and 500 pennies, do we arbitrarily decide that one is the lighter side, do we say there is no lighter side, or do we declare both sides to be the lighter side?

In the case of equal weight buckets, just arbitrarily pick one.
"It doesn't matter who you vote for, the government always gets in." -- Elizabeth May, Canadian Green Party Leader

AvalonXQ
Posts: 747
Joined: Mon Feb 18, 2008 5:45 pm UTC

### Re: Coins and Scales ... but not what you think.

Spoiler:
The lighter scale, with value n+1, occurs with a probability equal to:
(the chances of a certain configuration of n hits and 998-n misses) * (the number of different configurations of n hits and 998-n misses)
The chances of the certain configuration occurring are:

(n)!*(998-n)! / 999!

The number of different configurations are 998 choose n, or:

998!/n!*(998-n)!

So value n+1 occurs with probability 1/999

Any mistakes so far?

EDIT: Made a math error. Went back and corrected it. Now my answer fits with mbrownmx's as well, although it was calculated algebraically rather than by computer.

You've been here a while and you still don't spolierise?????????????????????????
Last edited by AvalonXQ on Fri Sep 05, 2008 8:54 pm UTC, edited 2 times in total.

mbrownmx
Posts: 24
Joined: Wed May 14, 2008 4:27 am UTC

### Re: Coins and Scales ... but not what you think.

I'm getting a value (with method) of
Spoiler:
250.250_

Before dropping the first coin, you're in a state of (1,1). After the first drop, you're in either state (1,2) or (2,1), both with probability 1/2. After the second, you're in (1,3), (2,2), or (3,1), the outer two with probability (1/2)*(2/3) [1/2 that you were in the appropriate (1,2) state, 2/3rds then that we land in the bucket with 2 coins] = 1/3, and the middle one of (1/2)*(1/3) + (1/2)*(1/3) = 1/3.

In general, the probability we're in a state with N on the left and M on the right after (N+M-2) drops (N+M coins total) is:
P(M,N) = 1 for M = N = 1.
0 for M <= 0 or N <= 0
P(M-1,N) * (M-1)/(M+N-1) + P(M,N-1)* (N-1)/(M+N-1), otherwise

Through brute force work, 'cause it was faster with a computer than trying to simplify that, it would appear that, in general, P(N,M) = 1/(N+M-1) for M>=1 and N>=1. [I think this is actually provable by induction; quick sketch: Clearly true for base case of (1,1); If we assume it's true for (M-1,1) and substitute in for (M,1), we get P(M-1,1)*(M-1)/(M) + P(M,0)*(0)/(M) = P(M-1,1)*(M-1)/(M) = 1/(1+M-1-1) *(M-1)/M = 1/(M-1)*(M-1)/M = 1/M; if we then assume for (M-1,N) and (M,N-1), we get P(M,N) = 1/(N+M-2)*(M-1)/(M+N-1) + 1/(N+M-2)*(N-1)/(M+N-1) = 1/((N+M-2)*(M+N-1))*(M-1+N-1) = 1/(M+N-1)]

Thus, each case of (1,999) through (999,1) is equally likely to occur. Expected value of a pair (M,N) = P(M,N)*MIN(M,N); overall pairs, we have each value 1...499 twice as a min, and 500 once; so we have (1+2+...499+500+499+...2+1)/999 = 250,000/999 = (the above)

To AvalonXQ:
AvalonXQ wrote:
Spoiler:
The lighter scale, with value n+1, occurs with a probability equal to:
(the chances of a certain configuration of n hits and 998-n misses) * (the number of different configurations of n hits and 998-n misses)
The chances of the certain configuration occurring are:

(n-1)!*(998-n)! / 999!

The number of different configurations are 998 choose n, or: 998!/n!*(998-n)!

So value n+1 occurs with probability 1/(n*999)

Any mistakes so far?

Maybe I'm missing something, but isn't the above assuming each coin is equally likely to hit either bucket? If I'm understanding what I'm reading correctly, you seem to be saying, after seeding (R,L,L.....L) and (L,L,...L,R) are equally likely, which they aren't.

Mountainhawk
Posts: 199
Joined: Tue Aug 19, 2008 11:23 pm UTC
Location: Salem, MA

### Re: Coins and Scales ... but not what you think.

mbrownmx wrote:I'm getting a value (with method) of
Spoiler:
250.250_

Before dropping the first coin, you're in a state of (1,1). After the first drop, you're in either state (1,2) or (2,1), both with probability 1/2. After the second, you're in (1,3), (2,2), or (3,1), the outer two with probability (1/2)*(2/3) [1/2 that you were in the appropriate (1,2) state, 2/3rds then that we land in the bucket with 2 coins] = 1/3, and the middle one of (1/2)*(1/3) + (1/2)*(1/3) = 1/3.

In general, the probability we're in a state with N on the left and M on the right after (N+M-2) drops (N+M coins total) is:
P(M,N) = 1 for M = N = 1.
0 for M <= 0 or N <= 0
P(M-1,N) * (M-1)/(M+N-1) + P(M,N-1)* (N-1)/(M+N-1), otherwise

Through brute force work, 'cause it was faster with a computer than trying to simplify that, it would appear that, in general, P(N,M) = 1/(N+M-1) for M>=1 and N>=1. [I think this is actually provable by induction; quick sketch: Clearly true for base case of (1,1); If we assume it's true for (M-1,1) and substitute in for (M,1), we get P(M-1,1)*(M-1)/(M) + P(M,0)*(0)/(M) = P(M-1,1)*(M-1)/(M) = 1/(1+M-1-1) *(M-1)/M = 1/(M-1)*(M-1)/M = 1/M; if we then assume for (M-1,N) and (M,N-1), we get P(M,N) = 1/(N+M-2)*(M-1)/(M+N-1) + 1/(N+M-2)*(N-1)/(M+N-1) = 1/((N+M-2)*(M+N-1))*(M-1+N-1) = 1/(M+N-1)]

Thus, each case of (1,999) through (999,1) is equally likely to occur. Expected value of a pair (M,N) = P(M,N)*MIN(M,N); overall pairs, we have each value 1...499 twice as a min, and 500 once; so we have (1+2+...499+500+499+...2+1)/999 = 250,000/999 = (the above)

To AvalonXQ:
AvalonXQ wrote:
Spoiler:
The lighter scale, with value n+1, occurs with a probability equal to:
(the chances of a certain configuration of n hits and 998-n misses) * (the number of different configurations of n hits and 998-n misses)
The chances of the certain configuration occurring are:

(n-1)!*(998-n)! / 999!

The number of different configurations are 998 choose n, or: 998!/n!*(998-n)!

So value n+1 occurs with probability 1/(n*999)

Any mistakes so far?

Maybe I'm missing something, but isn't the above assuming each coin is equally likely to hit either bucket? If I'm understanding what I'm reading correctly, you seem to be saying, after seeding (R,L,L.....L) and (L,L,...L,R) are equally likely, which they aren't.

This agrees with my intuition and the answer they give. I hadn't even considered looking at an induction-style argument, and now it seems obvious.
"It doesn't matter who you vote for, the government always gets in." -- Elizabeth May, Canadian Green Party Leader

AvalonXQ
Posts: 747
Joined: Mon Feb 18, 2008 5:45 pm UTC

### Re: Coins and Scales ... but not what you think.

mbrownmx wrote:
Maybe I'm missing something, but isn't the above assuming each coin is equally likely to hit either bucket? If I'm understanding what I'm reading correctly, you seem to be saying, after seeding (R,L,L.....L) and (L,L,...L,R) are equally likely, which they aren't.

Actually, I'm saying they are.
Spoiler:
Take a simple example that the final state is (2,4). This could be (L,R,R,R) or (R,R,R,L).
Now, the chance of (L,R,R,R) is 1/2*1/3*2/4*3/5
The chance of (R,R,R,L) is 1/2*2/3*3/4*1/5 ... exacty the same.
Specifically, both cases, and any other case with a final state of (2,4), will have probability (1*2*3*1)/(2*3*4*5)
In general, rearranging R's and L's while keeping the same number of each simply rearranges the numerators of the fractions you're multiplying together. The denominators stay the same (2 to 999), and the numerators are the same, just reordered. Since a/b*c/d = c/b*a/d for arbitrary a,b,c,d, this means each case is equivalent.

Also, fixed my math above, replacing an (n-1) with an n.

mbrownmx
Posts: 24
Joined: Wed May 14, 2008 4:27 am UTC

### Re: Coins and Scales ... but not what you think.

AvalonXQ wrote:
mbrownmx wrote:
Maybe I'm missing something, but isn't the above assuming each coin is equally likely to hit either bucket? If I'm understanding what I'm reading correctly, you seem to be saying, after seeding (R,L,L.....L) and (L,L,...L,R) are equally likely, which they aren't.

Actually, I'm saying they are.
Spoiler:
Take a simple example that the final state is (2,4). This could be (L,R,R,R) or (R,R,R,L).
Now, the chance of (L,R,R,R) is 1/2*1/3*2/4*3/5
The chance of (R,R,R,L) is 1/2*2/3*3/4*1/5 ... exacty the same.
Specifically, both cases, and any other case with a final state of (2,4), will have probability (1*2*3*1)/(2*3*4*5)
In general, rearranging R's and L's while keeping the same number of each simply rearranges the numerators of the fractions you're multiplying together. The denominators stay the same (2 to 999), and the numerators are the same, just reordered. Since a/b*c/d = c/b*a/d for arbitrary a,b,c,d, this means each case is equivalent.

Also, fixed my math above, replacing an (n-1) with an n.

Ah, ok. Right, that makes sense.

I think the math typo was what confused me, since that didn't agree with what I was getting.

alterant
Posts: 32
Joined: Fri Feb 15, 2008 1:34 am UTC

### Re: Coins and Scales ... but not what you think.

Good puzzle!

Spoiler:
I diagrammed it out using something like a Pascal's triangle and found that all the amounts of money are equally likely; there is no expected value - it could be anything. I did not prove this for the nth case or anything that fancy (only went up to 5 coin drops).

This ran against to my first intuition, which was that the coin drops were a sort of runaway process and that one side would eventually have way more than the other.

But my second, "counter"-intuition was that this sounded fishy, because there is no "nice" number related to the numbers in the problem that is between 501 and 1000. But it surely isn't a 50-50 split either! I didn't think of the alternative though, that all were equally likely.

+1 would solve again.

Christopher
Posts: 31
Joined: Sat Sep 27, 2008 3:57 am UTC

### Re: Coins and Scales ... but not what you think.

Well I get an answer and a nice general formula, but can't prove either of them (could prove the answer by calculating everything out, but I don't want to).

Spoiler:
Well I ran through the probabilities of the 3 through 9 coin cases. The EV's for these are as follows (The number of coins in my table includes the two initially placed into the buckets):

Coins Expected Value

3 1
4 4/3
5 3/2
6 9/5
7 2
8 16/7
9 5/2

Two patterns emerge, one for an odd number of coins and one for an even. For an odd number of coins, the general formula looks to be (n + 1)/4. For an even number of coins, the general formula looks to be [(n/2)^2]/(n - 1). Both of these approach n/4.

By these formulas, the answer to the problem is (500)^2/999 (about 250) as someone else has already posted. I haven't spent a whole lot of time since finding these patterns, but I would certainly like to have these general formulas proven. I would take an inductive proof, but I'd prefer a more illuminating one if possible. I'll work on it again some time when I have time.

Godskalken
Posts: 159
Joined: Wed May 14, 2008 3:29 pm UTC

### Re: Coins and Scales ... but not what you think.

Spoiler:
Well, since I spent some time on this, heres a formal proof using statisticss, and resting on one of the proofs given earlier.
Let's say we are putting n coins in after the initial 2. The probability of there being k coins in one chosen bucket after we finish is, as several others have shown, 1/(n+1), independent of k. Using standard statistics, we have the formula for the expected value:
E[k]=sum for all k of k*probability(k). In our context, $E[k]=\sum_{i=0}^n \frac{i}{n+1},$which is n/2. This is, not surprisingly, the expected value of the number of coins in one given bucket after the game. In order to find the expected value for the bucket with the least coins, we need to find E[k|k<=n/2], that is, the expected number of coins in a bucket given that this bucket has the fewest coins. In the formula for the expectancy, we must now use the conditional probability p(k|k<=n/2), which is defined as p(k,k<=n/2)/p(k<=n/2). The numerator is equal to p(k) for k<=n/2, and zero for k>n/2. The denominator is equal to 1/2 (or (n-1)/2*n if n is odd).
In other words, p(k|k<=n/2)=2/(n+1) for k<=n/2. Thus we have
$E[k|k\leq n/2]=\sum_{i=0}^{n/2} \frac{2i}{n+1}=2(n/2)(n/2+1)/(2(n+1))=\frac{n(n/2+1)}{2(n+1)}\approx n/4.$
The exact number for n=998 should then be 249.7497.