Monday, December 18, 2006

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?

2 Comments:

Blogger NoWhereMan said...

suba, combinatorics amele solve maadu ....hengidhya neenu? yen samachara? replye madalla .....naapka ideeva navella? .....

3:24 PM  
Blogger Aleph Null said...

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.

7:05 AM  

Post a Comment

<< Home