Problem in Combinatorics
Here is a problem in Combinatorics.
Consider a balloon seller who has n balloons of different color. The seller being rather loony sells only balloons in bunches of r and that too a random set of r balloons. The question is simple. How many time would you expect to go to the seller to buy before you have atleast one balloon of each color?
Consider a balloon seller who has n balloons of different color. The seller being rather loony sells only balloons in bunches of r and that too a random set of r balloons. The question is simple. How many time would you expect to go to the seller to buy before you have atleast one balloon of each color?
posted by Tracer Bullet at 9:25 AM
2 Comments:
suba, combinatorics amele solve maadu ....hengidhya neenu? yen samachara? replye madalla .....naapka ideeva navella? .....
I tried and as usual I failed. Anyway, this is the direction in which I am thinking:
Let X be the random variable which indicates the number of times I have to go to the seller. We want to find out E(X).
E(X) = Summation[x.P(X=x)] : summation runs from 1 to n.
P(X=x): The probability that Ceiling(n/r) = x.
The simple cases (assuming uniform distribution of r and assuming r remains same once decided initially by the seller) are:
x = 1, r = n, P() = 1/n
x = n, r = 1, P() = 1/n
x = 2, r = [n/2, n-1], P() = 1/2
After this I am stuck. Subbu, the saviour, I seek thy wisdom.
Post a Comment
<< Home