Ball Solutions

So, last time I introduced a ball problem, and I guess its time to show the solution. The solution is actually really simple, but I feel like doing a full-blown derivation.

First, let us define f(n,m) to be the solution to our problem, specifically it is how many black balls will be left if we started with n white and m black balls. We know f on the boundary cases:
1. f(0,m)=m
2. f(n,0)=0
To get the rest, consider that from a given position with n white balls and m black balls, we have a m/(n+m) chance to remove a black ball, and a n/(n+m) chance to remove a white ball. This means that:
f(n,m)=m/(n+m)*f(n,m-1)+n/(n+m)*f(n-1,m)
From here we can start to figure stuff out.

First, let us find f(1,m)
f(1,m)=m/(m+1)*f(1,m-1)+1/(m+1)*m
f(1,m)=m(m+1)*(f(1,m-1)+1)
From here, you can find f(1,1)=1/2, f(1,2)=1, f(1,3)=3/2 and guess f(1,m)=m/2. Alright, great, then a similar process on f(2,m) gives you that it is m/3, and this leads one to the general guess of f(n,m)=m/(n+1). Since it is already known to be true for the boundary cases, it suffices to show that when this formula holds for f(n-1,m) and f(n,m-1) it then holds for f(n,m). Something of a double induction:
f(n,m)=m/(n+m)*f(n,m-1)+n/(n+m)*f(n-1,m)
f(n,m)=m/(n+m)*(m-1)/(n+1)+n/(n+m)*m/n
f(n,m)=m/(n+m)*((m-1)/(n+1)+1)
f(n,m)=m/(n+m)*(m-1+n+1)/(n+1)=m/(n+1)
Yep, it works.

Actually, after the fact, you can intuit the answer in the limit of large m (does it still count as intuiting it after the fact?). If m is large, you can picture many black balls in a line, with a few white balls in the mix. If they are sorted randomly, and then taken from one end how many black balls will be after the last white ball? The white balls will evenly divide up the black balls into n+1 groups, and so at the end there will be m/(n+1) black balls.

No comments: