1

Suppose $11$ students show up for a meet-the-prof session to which Professor Grumble has brought $43$ identical cookies.

(1) How many ways can the cookies be distributed if everyone (including Prof. Grumble) gets at least $1$ cookie?

(2) How many ways can the cookies be distributed if Prof. Grumble gets at least 1 and everyone else gets at least $2$?

So far, I have: (a) P(43,12) = 43! / (43 - 12)! = 7347251430341222400 ways of distributing the cookies if everyone gets one cookie.

(b) C(43,1)*P(42,11) = 43 * (42! / (42 - 11)! ) = 43*170866312333516800 = 7347251430341222400 ways of distributing the cookies.

Those numbers seem huge. Did I do this right?

Thanks, D

  • 1
    This is missing a great deal of information. How many cookies are there? How many people are there? What types of cookies are they? Are they all the same or different? Must all cookies be used? – JMoravitz Aug 08 '16 at 19:17
  • Suppose 11 students show up for a meet-the-prof session to which Professor Grumble has brought 43 identical cookies. – Dan Marchisella Aug 08 '16 at 19:23
  • An answer of $P(43,12)=\frac{43!}{(43-12)!}$ makes sense if all $43$ of the cookies are different and everyone gets exactly one cookie (note the difference between "exactly one" and "at least one") – JMoravitz Aug 08 '16 at 19:23
  • You still haven't answered the question of whether or not all cookies must be used. – JMoravitz Aug 08 '16 at 19:25
  • OH! I didn't see that at first. How would this change for at least one)? – Dan Marchisella Aug 08 '16 at 19:25
  • it doesnt specifiy weather all cookies must be used – Dan Marchisella Aug 08 '16 at 19:30
  • Usually the people are distinguishable, while the cookies (as described here) are indistiguishable (identical). What you are asking about are compositions of $43$ (ways to express $43$ as an ordered sum) with various restrictions on number of summands and their sizes. – hardmath Aug 08 '16 at 19:34

1 Answers1

3

Now that we know how many people and cookies there are, and that all cookies are identical we still have two different possible interpretations for the question. Either all cookies must be used, or you can have some leftover. I will try to explain both.


In the case that we have $43$ identical cookies, and $12$ people total (which includes the professor) and we are looking to use all of the cookies, we try to reword the question into a more mathematical context that we are (hopefully) more familiar with.

Let $x_1,x_2,\dots,x_{12}$ be the number of cookies that the first person, second person, etc... receive respectively. (for example, $x_1$ is number of cookies student1 gets, $x_2$ is number of cookies student2 gets,...). By the fact that we are told we want to use all of the cookies, that implies that $x_1+x_2+\dots+x_{12}=43$ and furthermore that each of the $x_i$ are non-negative integers.

In the first problem, we want to ensure that everyone gets at least one cookie, i.e. that $1\leq x_i$ for each $i$. This implies the system of equations:

$$\begin{cases} x_1+x_2+x_3+\dots+x_{12}=43\\ 1\leq x_1\\ 1\leq x_2\\ \vdots\\ 1\leq x_{12}\end{cases}$$

Depending on how you were taught, this might be the well known form of the problem that you should have memorized and you can jump straight to the answer. I personally learned the answer to the form where the lower bound is $0$ for every variable instead of $1$ for each lower bound. To transform it into where zero is the lower bound for everything, make a change of variable, setting $y_i=x_i-1$ for each $i$ giving the system:

$$\begin{cases}y_1+y_2+y_3+\dots+y_{12}=31\\ 0\leq y_1\\ 0\leq y_2\\ \vdots\\ 0\leq y_{12}\end{cases}$$

Regardless which form you are more comfortable with, we know from earlier example that the number of integer solutions to the system is $\binom{31+12-1}{12-1}=\binom{42}{11}$


In the case that we do not require that all of the cookies be used, we include an extra variable for the system, $x_{13}$, where $x_{13}$ represents the number of unused cookies.

That is to say, the number of solutions to the system $\begin{cases}x_1+x_2+\dots+x_{12}\color{red}{\leq} 43\\ 1\leq x_1\\ 1\leq x_2\\\vdots\\1\leq x_{12}\end{cases}$

is the same as the number of solutions to the system $\begin{cases}x_1+x_2+\dots+x_{12}+\color{red}{x_{13}=}43\\1\leq x_1\\ 1\leq x_2\\ \vdots\\ 1\leq x_{12}\\ 0\leq x_{13}\end{cases}$

Approach similarly by making a change of variable to put this into a well known form and arrive at a conclusion.


For the second part of the question, approach similarly to the first part, but the lowerbounds will be different. Letting professor grumble be the "first person", we have the system $\begin{cases} x_1+x_2+\dots+x_{12} \color{red}{=~\text{or}~\leq}43&\color{red}{\text{depending on interpretation}}\\ 1\leq x_1\\ 2\leq x_2\\ 2\leq x_3\\ \vdots\\ 2\leq x_{12}\end{cases}$


For information on why the number of solutions to the system $\begin{cases} x_1+x_2+\dots+x_k = N\\ 0\leq x_1\\ 0\leq x_2\\ \vdots \\ 0\leq x_k\end{cases}$ is equal to $\binom{N+k-1}{k-1}$, see this answer.

The short version is that you can describe any way of distributing the cookies as an arrangement of stars and bars. $\circ\mid\circ\circ\circ\mid\circ\circ\mid\mid\circ\circ\dots$ for example would correspond to the first person getting one cookie, the second person getting three cokies, the third person getting two cookies, the fourth person getting no cookies, etc...

That is, we can place dividers between the cookies, and depending on where the dividers are, we split up the cookies that way between the people. We need to use one fewer divider than the number of people (in the case that all cookies must be used, or the same number of dividers as people in the case that we can have leftover cookies). By choosing the locations of the dividers, we get the total number of arrangements.

Some people as mentioned learned how to count the solutions to the system with the lower bound being $1$ in every case before learning how to count with the lower bound being $0$ in every case. (Even @AndréNicolas learned it this other way). Read the linked comments for some more info on how to justify that interpretation.

JMoravitz
  • 79,518