0
$\begingroup$

I have 173 million pieces of candy. There are 5 students. In how many ways can this distribution be made, assuming that each student receives at least 1 million candies, Student B receives at most 10 million candies, and Student C receives at most 30 million candies, and Student D is to receive at least 5 million candies?

I can do this with a generating function, but have no idea how to approach this with inclusion and exclusion.

$\endgroup$
  • $\begingroup$ Naming them student B, C, and D is confusing. Where is student A? $\endgroup$ – Mike Pierce Feb 24 '15 at 23:48
  • $\begingroup$ @mapierce271 Student A is just set to receive at least 1 million candies. All I'm trying to say is that of the 5 students, 3 of them have their own unique requirements. $\endgroup$ – Nxt3 Feb 24 '15 at 23:53
2
$\begingroup$

Give one million candies to $A,B,C,E$ and five million to $D$ (We have to do it anyways so lets get it out of the way). We now have $164$ million and the only requirements are that $B$ gets at most $9$ million and $C$ gets at most $29$ million.

There are $\binom{164,000,004}{4}$ ways to distribute the coins ignoring the upper limit to the candy for $B$ and $C$ because of stars and bars.

Now use inclusion exclusion: How many ways are there in which $B$ gets more than $9$ million(Call this $b$). How many ways are there in which $C$ gets more than $9$ million (Call this $c$), how many ways are there in which $B$ gets more than $9$ million and $C$ more than $29$ million(call this $m$)?

You can solve each of these problems via stars and bars.

at the end your solution will be

$\binom{164,000,004}{4}-b-c+m$ by inclusion exclusion.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Are $b, c \space and \space m$ exclusive? Are we going to figure out $b$ using the total number of candies (173m), or 164m? $\endgroup$ – Nxt3 Feb 25 '15 at 0:39
  • 1
    $\begingroup$ Using 164. $a$ $b$ and $m$ are not exlusive. You have to substact the $b$ bad cases, the bad $c$ cases and then add back the $m$ cases which are in both $b$ and $c$ and where substracted twice. $\endgroup$ – Jorge Fernández Hidalgo Feb 25 '15 at 0:48
  • 1
    $\begingroup$ It should be chose 4, I made a typo. I don't understand the first wuestion though. $\endgroup$ – Jorge Fernández Hidalgo Feb 25 '15 at 0:55
  • 1
    $\begingroup$ Oh yeah, my bad. $\endgroup$ – Jorge Fernández Hidalgo Feb 25 '15 at 0:59
  • 1
    $\begingroup$ You have to use stars and bars. First give $9,000,001$ to $B$. You now have $154,999,999$ candies to give freely. So there are $\binom{155,000,003}{4}$ ways to give out the candies. So $b$ is that binomial coefficient. $\endgroup$ – Jorge Fernández Hidalgo Feb 25 '15 at 1:20

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.