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

        riddles >> medium >> Balls in Holes
        
(Message started by: HiddenHeart on Jan 17th, 2008, 12:44am)
Title: Balls in Holes
Post by HiddenHeart on Jan 17th, 2008, 12:44am
n balls are thrown into n holes. The experimental setup is such that each ball must find some hole to enter. Each hole can accommodate any number of balls.
The problem is:
1. What is the probability of exactly one hole being empty? [easy]
2. What is the probability of exactly two holes being empty? [medium]
3. What is the probability of having any k<n number of empty holes? [hard if you don't know about 'Stirling numbers of the second kind']
Title: Re: Balls in Holes
Post by jollytall on Jan 17th, 2008, 4:20am
For k=0. n!/nn.

For k=1. Let's assume one ball is different in colour. What is the probability that all normal colour balls are in separate holes, but the special one is next to a normal one. The probability that all normal ones are in different holes is n*n!/nn. The probability that the special one fell in an already used one is (n-1)/n. So the probability that it all happens at ones is (n-1)*n!/nn. But all can be special colour, so the probaility is n times higher, i.e. n*(n-1)*n!/nn. Now the only problem that every potential "good" outcome we counted twice (either of the two balls in one hole can be read. So my final number is
n*(n-1)*n!/2/nn.

Another solution for the same k=1:
Let's number the balls from 1..n. There are all together nn potential outcome. Now let's count the "good" outcomes. If everything is fixed, i.e. which two balls share a hole, which hole they share and which whole is empty, then there are (n-2)! solutions (n-2 balls put into n-2 holes). This is (n-2)!/nn. The empty hole we can choose n ways. The double hole we can shoose n-1 ways. So we are at n!/nn. The two balls that share the hole we can choose n*(n-1)/2 ways. So the final result is just the same as above.
Title: Re: Balls in Holes
Post by HiddenHeart on Jan 17th, 2008, 4:40am
Well done jollytall !

But the problem still remains open for k>1
[at least here  ;) ]
Title: Re: Balls in Holes
Post by jollytall on Jan 17th, 2008, 4:41am
For k=2 it is still doable the same way, though gets a bit messy.
There are two ways. Either three balls share one hole or 2x2.
The first: The tho empty and the triple hole we can choose n*(n-1)/2 * (n-2) ways. The three balls that share the hole we can choose n|3 ways. The rest n-3 balls go into n-3 holes in (n-3)! ways. So it is n!/nn * (n|3)/2 - where n|m is n!*(n-m)!/m!
The second (only for n>3): The two empty and two double holes we can choose n*(n-1)/2 * (n-2)*(n-3)/2 ways. The four balls we can choose n|4 ways. The rest n-4 balls can be put in the n-4 holes (n-4)! ways. So it is
n!/nn * (n|4)/4.
The total is therefore:
n!/nn * ( (n|3)/2+(n|4)/4).

P.S. Sorry for the n|m format, but I could not find another easy one :-)
Title: Re: Balls in Holes
Post by HiddenHeart on Jan 17th, 2008, 5:41am
:)

yap you are really close!!

for n=4 and k=2

we have the probability 21/64

where as your(jollytall's) formula results into 27/128

still i say you that you are really close because your 'the second' case has a slight flaw!!

when you chose 4 balls and 2 holes where you want to put them pairwise you just counted (n|4) !!

you can make pairs from 4 balls in 3 ways[select a ball and choose its partner in 3 ways]
and you can put each pair of pairs in 2 holes in 2 ways. in total 3*2 = 6 way!!

so the formula of the second part would be multiplied by a factor of 6.
that is it would be  n!/nn * (n|4)/4 *6

the whole answer will be then
n!/nn * ( (n|3)/2+3(n|4)/2).

which conforms to our result for (n,k)=(4,2) of 21/64  :)
which i generated from quit a different [general] solution of this problem.

PS: by the way, i liked the n|m notation. its kind of cute! :)
[and still its open for k>2 ;) ]
Title: Re: Balls in Holes
Post by jollytall on Jan 17th, 2008, 7:03am
I told it gets messy :-)

Yes, the second step must be multiplied by 4|2, as the four "double" balls can be split into the 2 holes 6 ways.
With other words it is not n|4, but n|4 * 4|2. This result can also be got, if I say n|2 * (n-2)|2, i.e. first choose 2 balls for the first double hole and then the next 2.
Title: Re: Balls in Holes
Post by Icarus on Jan 18th, 2008, 8:43pm

on 01/17/08 at 00:44:43, HiddenHeart wrote:
n balls are thrown into n holes. The experimental setup is such that each ball must find some hole to enter. Each hole can accommodate any number of balls.
The problem is:
1. What is the probability of exactly one hole being empty? [easy]
2. What is the probability of exactly two holes being empty? [medium]
3. What is the probability of having any k<n number of empty holes? [hard if you don't know about 'Stirling numbers of the second kind']


Let's see. In my experiment,

1) 100% for n=2; 0% for n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 2.
2) 100% for n=3; 0% for n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 3.
3) 100% for n=k+1; 0% for n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif k+1.

In my experiment, I simply drop all the balls into the first hole!

(A minor nitpick. Obviously you meant that the balls are equally likely to enter each of the holes. But since you never indicated this, I'll just exploit the loophole!)
Title: Re: Balls in Holes
Post by ThudanBlunder on Jan 18th, 2008, 11:55pm

on 01/17/08 at 00:44:43, HiddenHeart wrote:
[hard if you don't know about 'Stirling numbers of the second kind']

They seem to ring a Bell (http://mathworld.wolfram.com/BellNumber.html).


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board