2
$\begingroup$

How many ways there are to distribute $400$ non distinct balls to $3$ bins such that in all of the bins there are more than $200$ balls or less than $100$ balls.

My attempt:

Notice there's only one bin with at least $202$ balls, there are $3$ ways to choose it.

Now we're left with $198$ balls and two bins such that both will hold $99$ balls at most, using complement: one of the bins will hold more than $99$, there are $2$ ways to choose which bin.

The general case: $\binom {198+2-1}{2-1}$, we'll fill that bin with $100$ balls and we're left with $98$ balls to distribute to $2$ bins: $\binom {98+2-1}{2-1}$

So the total would be: $3\cdot 2(\binom {198+2-1}{2-1}-\binom {98+2-1}{2-1})$

I'm not sure I'm using the complement correctly here.

$\endgroup$
  • $\begingroup$ Are the bins distinguishable? $\endgroup$ – TravisJ Mar 12 '15 at 19:17
  • $\begingroup$ @TravisJ it doesn't say, so I think they're indistinguishable. $\endgroup$ – shinzou Mar 12 '15 at 19:22
  • $\begingroup$ The problem is much easier if they are distinguishable... I'd personally default to distinguishable (since I could line up static bins). $\endgroup$ – TravisJ Mar 12 '15 at 19:24
  • $\begingroup$ Since in a different question they specify that the bins are 'distinct' then I think here it means the bins are non distinct but I wouldn't mind seeing how it makes a difference. @TravisJ $\endgroup$ – shinzou Mar 12 '15 at 19:30
  • $\begingroup$ If the bins are distinguishable, you can use a method like stars and bars (en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29). I think it'll be easiest to count the total number of placements then subtract off the bad ones. $\endgroup$ – TravisJ Mar 12 '15 at 19:38
1
$\begingroup$

You have a good start. You know that you have to have at least 202 balls in one box, and 99 or less in both others.

EDIT: I am assuming this problem is using distinct bins (as 99% of all balls-in-bins problems I've encountered are non distinct balls in distinct bins). The concept I used will still apply for non distinct bins, but the math becomes a little more complex.

So we can view this problem as the addition of the number of possible outcomes from having 202-400 balls in the largest box.

In the case that there were 400 balls in 1 box, and none in any other, your number of ways turns out to be 3- the number of possible boxes to hold the 400 balls. For 399, you have 3 possibilities for the large box, then 2 possibilities for the box with 1 ball. This gives 3*2=6. You can pretty easily extrapolate this formula to be N(b)=3*(401-b). This formula only works while b is less than or equal to 400, and greater than or equal to 301 (the midpoint between 202 and 400). The summation of the number of outcomes from 202 to 301 is equal to the summation from 301 to 400 (as both 400 and 202 balls in the largest box only allow for 3 possible outcomes).

Therefore, you can express the final answer as $2 * \sum\limits_{i=302}^{400}N(i)+N(301)$. Plugging this into our equation above gives the answer: $30000$

$\endgroup$
  • $\begingroup$ Is there a way to do this without the generating function? We haven't covered that yet and I don't see how you got to it easily... $\endgroup$ – shinzou Mar 12 '15 at 20:03
  • $\begingroup$ Sorry, I just kind of played around with the idea that we have 3 possible outcomes for 400 balls in the largest bin, then 6 for 399, then 9 for 398, etc. You could figure it out from there with a pretty simple y intercept and slope problem (slope being -3, and y intercept calculates out to 1203). $\endgroup$ – Steven Kneisler Mar 12 '15 at 20:33
  • $\begingroup$ Why is it 9 for the 398? isn't it $3\cdot 2^2$? i.e 3 options for the 398 and 2 options for each of the two balls. $\endgroup$ – shinzou Mar 14 '15 at 19:27
  • $\begingroup$ You're thinking correctly, but it's only 9 instead of $3*2^2$ because in the scenario where you have 1 ball in each of the smaller bins, as the balls are not distinct, switching those balls around does not give you another possible outcome. $\endgroup$ – Steven Kneisler Mar 16 '15 at 3:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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