I am a mango -_-

Probability Level 3

If you are given $\color{#20A900}{\textbf{18 raw mangoes}}$ , $\color{#D61F06}{\textbf{14 ripe mangoes}}$ and $\color{#624F41}{\textbf{10 rotten mangoes}}$ , how many different groups of $20$ mangoes can you form such that there are at least $5$ mangoes of each type ?

$\bullet$ This problem is a part of the set Vegetable combinatorics

The answer is 21.

3 solutions

Ivan Koswara
Jul 24, 2014

Let there be $w$ ra w mangoes, $e$ rip e mangoes, and $n$ rotte n mangoes. Then the problem is equivalent to finding the number of integer solutions to $w+e+n = 20$ , $5 \le w \le 18$ , $5 \le e \le 14$ , $5 \le n \le 10$ .

Observe that given $w+e+n = 20$ and the lower bounds $5 \le w,e,n$ , all upper bounds are satisfied; if any type of mangoes go over the upper bound while the lower bounds are all satisfied, then the sum gets over $20$ . For example, if $n > 10$ while $w,e \le 5$ , we have $w+e+n > 20$ . Thus we may as well ignore the upper bounds. Now let $a = w-5, b = e-5, c = n-5$ so we have $a+b+c = 5$ and $0 \le a,b,c$ . This is a basic combinatorics problem, where the number of solutions is $\dbinom{5+3-1}{3-1} = \boxed{21}$ .

Note that 7C2 is obtained through the Stars and Bars Theorem. More info about it can be found here: http://en.wikipedia.org/wiki/Stars and bars_(combinatorics)

Linus Setiabrata - 6 years, 10 months ago

nice solution..

manish bhargao - 6 years, 3 months ago

Nicolas Bryenton
Aug 4, 2014

I just used the stars and bars.

There must be at least 5 of each, so if we assume there are already four from each group picked, the stars and bars theorem will guarantee that there will be at least 5. So using the stars and bars on 8 (20-3(4)) and 3 gives 7C3=21

N.B.: since there must be at least 5 of each, the max you can have of one is 10, so the stars and bars falls within the parameters of the question.

Cody Johnson
Jul 24, 2014

Generating functions.

Hi! Please could you explain how you solved it using generating functions? I'm quite new to the topic. Thanks

Soham Karwa - 6 years, 10 months ago

Let a be raw mangoes, b be ripe and c be rotten mangoes.

Now, each must be at least 5, so

$a + b + c = 20 - (5*3)$

$a + b + c = 5$ and $a \le 5, b \le 9, c \le 13$

Now, the generating function for this becomes -

$(1 + x + ... + {x}^{5})(1 + x + ... + {x}^{9})(1 + x + ... + {x}^{13})$ in which we have to find co-efficient of ${x}^{5}$ .

$\frac{1 - {x}^{6}}{1-x}\frac{1 - {x}^{10}}{1-x}\frac{1 - {x}^{14}}{1-x}$

$({(1-x)}^{-3})(1 - {x}^{6})(1 - {x}^{10})(1 - {x}^{14})$

Now, the last 3 are just trivial because all the positive powers of x are greater than 5. So, we just have to find the co-efficient of ${x}^{5}$ in ${(1-x)}^{-3}$ and we know that co-efficient of ${x}^{k}$ in ${(1-x)}^{-n}$ is $C(k + n -1, k)$ . Hence, the answer is $C(7,5) = 21$

Kartik Sharma - 6 years, 5 months ago

Absolutely correct,

Dinesh Chavan - 6 years, 10 months ago

I am a mango -_-

The answer is 21.

3 solutions

0 pending reports