Author |
Topic: Balls in Holes (Read 1231 times) |
|
HiddenHeart
Newbie
Gender: 
Posts: 24
|
 |
Balls in Holes
« on: Jan 17th, 2008, 12:44am » |
 Quote  Modify
|
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']
|
| « Last Edit: Jan 17th, 2008, 4:49am by HiddenHeart » |
 IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Balls in Holes
« Reply #1 on: Jan 17th, 2008, 4:20am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
HiddenHeart
Newbie
Gender:
Posts: 24
|
|
Re: Balls in Holes
« Reply #2 on: Jan 17th, 2008, 4:40am » |
Quote Modify
|
Well done jollytall !
But the problem still remains open for k>1
[at least here  ]
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Balls in Holes
« Reply #3 on: Jan 17th, 2008, 4:41am » |
Quote Modify
|
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 
|
|
IP Logged |
|
|
|
HiddenHeart
Newbie
Gender:
Posts: 24
|
|
Re: Balls in Holes
« Reply #4 on: Jan 17th, 2008, 5:41am » |
Quote Modify
|
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 ]
|
| « Last Edit: Jan 17th, 2008, 5:44am by HiddenHeart » |
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Balls in Holes
« Reply #5 on: Jan 17th, 2008, 7:03am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Balls in Holes
« Reply #6 on: Jan 18th, 2008, 8:43pm » |
Quote Modify
|
on Jan 17th, 2008, 12:44am, 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  2.
2) 100% for n=3; 0% for n 3.
3) 100% for n=k+1; 0% for n 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!)
|
| « Last Edit: Jan 18th, 2008, 8:43pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Balls in Holes
« Reply #7 on: Jan 18th, 2008, 11:55pm » |
Quote Modify
|
on Jan 17th, 2008, 12:44am, HiddenHeart wrote:| [hard if you don't know about 'Stirling numbers of the second kind'] |
|
They seem to ring a Bell.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print