Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We got 30 balls which are not distinguishable. We want to put them into 4 boxes A,B,C,D ,which are distinguishable, such that the number of balls in A is $\geq 10$ and in $B+C\leq 17$. This is equivalent to $\# \{(a,b,c,d) \in \mathbb N_{\geq 0}^4 \mid a \geq 10, b+c \leq 17, a+b+c+d = 30\}$.

How can I begin ?

My approach: Denote $\alpha(k)$ as the number of possibilities to put $k$ balls in $B$ and $C$ and $\beta(k)$ as the number for $B,C$ and $ D$.

Then if $a=10$ we have $d \in \{3,4,\cdots,20\}$ and get $\sum_{d=3}^{20} \alpha(20 -k)$. The same for $a =11$ and $a=12$. For $a \geq 13$ we have to put the rest of the balls into $B,C$ and $D$ without restriction which gives $\sum_{k=0}^{17} \beta(k)$ possibilites. Now add all the stuff and I hope we get the result.

Further is $\alpha(k) = 2+k-1$ and $\beta(k) = \binom{3+k-1}{2}$

This approach results in 1653 possibilities.

Suggestions would be nice :)

share|improve this question
1  
I think you mean $d\in[3,20]$ where it says $d\in\{3,20\}$. –  joriki Apr 8 '13 at 10:34

1 Answer 1

up vote 1 down vote accepted

Since $A$ needs at least $10$, put $10$ balls there. Now we need to distribute $20$ balls between $A$, $B$, $C$, and $D$ so that together $B$ and $C$ get $\le 17$.

$1.$ Find the number of ways to distribute $20$ balls between our four people, not paying any attention to the restriction about $B$ and $C$. I expect you have a standard Stars and Bars way of counting the number of ways to do this.

$2.$ But in $(1)$ you have counted some forbidden configurations, namely the ones in which between $B$ and $C$ we have (i) $18$; (ii) $19$; (ii) $20$.

Count all these bad configurations separately. For example, how many with $18$ between $B$ and $C$? There are $19$ ways to distribute the $18$ balls between $B$ and $C$. And for each of these there are $3$ ways to distribute the other $2$ between $A$ and $D$. Do the same sort of calculation for (ii) and for (iii).

Finally, subtract the total number obtained in $(2)$, that is, the sum of (i), (ii), and (iii), from the number obtained in $(1)$.

There is also a generating functions approach, probably overkill, and no easier.

share|improve this answer
    
Thanks. I love generating functions but yeah. This is an (practice)exam question so it should be solvable quite fast. I try to work out your method and see in what it results. Question: Do I have to sum over $\#A \in \{10,11,\cdots,30\}$ ? –  André Apr 8 '13 at 10:40
    
I have described how to do it. No summing. This is really about distributing $20$ balls. –  André Nicolas Apr 8 '13 at 10:46
    
This is great :) Makes it a lot easier and gives indeed the same result. –  André Apr 8 '13 at 10:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.