Here’s a neat problem I saw in a recent post by Steven Miller on the Williams College math department blog. The problem comes from an old Putnam competition, one of the most prestigious college mathematics competitions. (It’s also one of the most difficult—out of a possible 120 points, the median score is 1!)
There are ten identical cookies and five students. How many ways can the cookies be distributed among the students?
Note that the cookies are identical, so it doesn’t matter which cookies a student gets, just how many. The students, of course, are not identical, so student A getting four cookies and student B getting two is different than A getting two and B getting four. Assume that the cookies can’t be split into pieces. Note that giving cookies to some students but not others is a valid way of distributing them, as long as all the cookies are distributed. For example, giving six cookies to student A, four to student C, and none to anyone else is a valid distribution.
My wife and I had a fun time solving this problem, which leads to all kinds of interesting combinatorial insights. I’ll describe our
analysis in an upcoming post.
The Math Less Traveled 
i may be wrong, but a simple way to do this is to consider permutations of the string “cccccccccc||||”, where the c’s are the cookies, and the |’s break up the cookie distribution into 4 buckets. of course the c’s are indistinguishable.
some examples would be
ccc|ccc|ccc|c|
cc|cc|ccc|cc|c
and it’s pretty easy to see how this translates into dividing the cookies between students.
i believe a formula would be (r + n – 1)! / [(n -1)! * r!] which you can convert to (r+n-1) C [(n-1)!*r!], which is my poor way of expressing combinations.
of course i meant 5 buckets, one for each student ;).
Let there be
cookies and 
students. Denote the number of ways to distribute 
cookies between 
students by 
. This is claiming that for a given number of students, the number of ways to distribute the cookies is a function of the number of cookies.
The last student can receive anywhere from
to 
cookies. Suppose he receives 
. Then there are 
cookies to distribute between 
students. This can be done 
ways. Summing over all possible values of 
we obtain
We know
because if there is one student, he must get all the cookies (AWESOME!).
Then
So the answer is 935. For larger
I conjecture,
which you could attempt to prove by induction.
sorry about the LaTeX, hope it’s still readable
Hi meichenl, I took the liberty of correcting the LaTeX for you, on my blog you can create LaTeX by enclosing things in [ tex ] and [ /tex ] (without the spaces)… it’s a bit different than wordpress.com since it’s using a slightly different system.
Anyway, your approach is a good one, but I think you went awry when computing S_3(c)…
Using meichenl’s notation:
So:
Just trying to be cute. Find five more cookies, and give each person one. Starting condition. Then have each put their cookie in the pile. So now we have 15 cookies, and each person must be returned at least their original cookie.
so 15 cookies, with 14 gaps between cookies, and place 4 dividers into any 4 distinct gaps: C(15,4)
(really, same as Mike, above)
Hi Brent,
Thanks for the typesetting info. You’re right – I started going wrong on
. I think I forgot to start counting at zero. Reworking it, I get:
Now conjecture
Which is the same as Mike’s expression. I took a look at the inductive step, but it’s not obvious to me how to do it.
The answer I get is C(14,4), not C(15,4), although I admit I can’t figure out what’s wrong with Johnathan’s explanation.
I wrote a quick script to generate all of the possible allocations and I got 1001 of them, and I’m pretty sure there aren’t any missing.
So perhaps the argument should be “14 gaps and 4 dividers: C(14,4)”.
@ Mark James:
Did your script really work by generating all of the possible assignments? Using the set of equations you gave in your earlier comment, it’s easy to give a compact and fairly efficient solution using dynamic programming: http://pastebin.com/f5076936. But this doesn’t actually enumerate assignments; it just counts them.
If you write
as a recursive function, when you get to the base cases 
, you’ve only got one possible allocation left. If you’re keeping track as you recurse, you can just print out the allocation at that point.
I don’t have the script here, but I’ll post it tonight.
It’s pretty simple code, so I just wrote it again. Sorry for the ugly perl.
http://pastebin.com/m44aa3feb
0 0 0 0 10
0 0 0 1 9
0 0 0 2 8
0 0 0 3 7
0 0 0 4 6
0 0 0 5 5
0 0 0 6 4
0 0 0 7 3
0 0 0 8 2
0 0 0 9 1
…
8 0 2 0 0
8 1 0 0 1
8 1 0 1 0
8 1 1 0 0
8 2 0 0 0
9 0 0 0 1
9 0 0 1 0
9 0 1 0 0
9 1 0 0 0
10 0 0 0 0
1001
I did something similar and got 1046.
I just did a similar problem with a student I was tutoring. It went something like “how many ways can the letters in ‘DALLAS’ be rearranged?”
The solution was 6!/(2!*2!) because there are 6 letters in “DALLAS” with 2 sets of 2 repeating letters (“A” and “L”). what Mike suggested fits right into this:
How many ways can 00000000001111 be rearranged? 14!/(10!*4!)=1001 the same answer as (almost) everyone else.
I’m not offering any new information here, but is there a way to solve this with binary numbers? It seems like if “0” is to mean “cookie” and “1” is to mean “divider between people” (as I have it above) then each possibility can be represented by a binary number. I don’t know how you’d go about doing that, I just thought it’d be cool.
I used a simplified version of some of the methods posted above. I thought about dividing up the 10 cookies as “making cuts.” For instance, you have 10 cookies, so there are 9 possible cuts that can be made in the spaces between those 10 cookies. If you make 0 cuts, then 1 person will be given all the cookies. If you make 1 cut, then 2 people will receive cookies. If you make 2 cuts, then 3 people will receive cookies…..If you make 4 cuts, then all 5 students will receive cookies. Or more generally, if you make n cuts, then n+1 people will receive cookies.
So the problem is just summing up all the ways that the cookies can be distributed when 0,1,2,3, and 4 cuts are made. This is a simple summation.
For 0 cuts, we want to know how many ways we can choose 0 cuts from 9 possible cuts and then how many ways we can distribute the resulting section of cookies to the 5 people. The product is the number of ways that all 10 cookies can be distributed to one of the people. So we calculate 9 CHOOSE 0 * 5 CHOOSE 1 and this will give us the total number of ways that all 10 cookies can be given to one person.
For 1 cut (remember that with 1 cut, 2 people will receive cookies), we calculate 9 CHOOSE 1 * 5 CHOOSE 2.
For 2 cuts (3 people receive cookies), we calculate 9 CHOOSE 2 * 5 CHOOSE 3.
You’ve probably already noticed a pattern. In order to distribute cookies to n people we need to make (n – 1) cuts. So to figure out the number of ways that cookies can be distributed to n people, we just calculate 9 CHOOSE (n – 1) * 5 CHOOSE n.
And now we are ready for our summation:
5
Σn = 1 ( 9 CHOOSE (n – 1) * 5 CHOOSE n )
Sorry about the weird looking notation.
@Nick:
I think binary numbers are kind of a red herring, since what we really care about is the combinatorial structure of sequences of 1’s and 0’s, or cookies and fences, or whatever you want to call them—the fact that strings of 1’s and 0’s can be interpreted as numbers doesn’t really help since we aren’t going to do arithmetic with them. If there WAS a way that binary arithmetic corresponded nicely to something in the problem, that would be neat, but I don’t think there is.
Anyway, nice analysis—indeed, you’re talking about multinomial coefficients, of which binomial coefficients are a special case. In general there are n!/(a! b! c! …) ways to permute n objects where a group of a are identical, a group of b are identical, and so on, and a + b + c + … = n.
Pingback: Distributing cookies: solutions « The Math Less Traveled
Pingback: Math Teachers at Play #5 « Let’s Play Math!
Was notified from a friend about this problem yesterday, and solved it by myself along the same line as Mike originally:
Look at it as placing 10 cookies (‘c’) and 4 markers (‘|’) in random order, the markers separating which cookies each student will get in turn.
Now the only thing we really are interested in here is the number of different ways we can select the 4 placeholders into which to put the markers, no matter what the order of the markers (and the cookies) are. This is expressed exactly as the combinatorial:
C(14, 4) = 14! / 4! 10!
That simple!
Seems that by now the post of the code to print out the combinations has expired. Sadness. I don’t understand perl well enough to translate the other post that just counted the possibilities. Would someone be willing to re-post that or describe the algorithm that would generate the “permutations” in this scenario? I would think it would be just a few lines of code but my brain hurts and I’m not coming up with it.
Chetmun: Here’s the algorithm to distribute c cookies to n students. The base cases are c = 0 (no cookies, so everyone gets 0) and n = 1 (the last student gets all the cookies). Otherwise, for each k from 0 to c, give the first student k cookies (remember this somehow, e.g. in an array), and recursively distribute (c – k) cookies to the remaining (n – 1) students. Each time you get to the last student, print out/save the current distribution of cookies which you have been remembering along the way.
Pingback: Distributing cookies: solutions | The Math Less Traveled
Thanks for posting Brent; really enjoyed reading the comments this started. Once my Riddles page is fully operational (right now I have a rush request to get the Death
Star ready before the Rebel Alliance arrives, and, well, finances are tight and the emperor pays well), I’ll link to this post.
Some comments:
1/ If anyone knows which Putnam this is from, I’d love to know. I first heard this riddle sometime b/w 1996 and 1998 when I was
helping undergrads at Princeton.
2/ Nick wrote: Im not offering any new information here, but is there a way to solve this with binary numbers? It seems like
if 0? is to mean cookie and 1? is to mean divider between people (as I have it above) then each possibility can be represented
by a binary number. I dont know how youd go about doing that, I just thought itd be cool. There is a way to do this using
0s and 1s; it’s essentially the same as the ways above, but perhaps this formulation will mean something to someone. Consider
(x+y)^14. This can be written as Sum_{k=0 to 14} (14 choose k) x^(14-k) y^k. We let x represent a cookie (your 0) and y
represent a divider (a 1). The coefficient of x^10 y^4 is the number of ways to have 10 cookies and 4 dividers, which is
exactly what we want! This is exactly what we want!
3/ If we want to put in some constraints such as everyone gets at least one cookie, that’s no problem. What we’re really doing
here is solving the equation x1 + x2 + x3 + x4 + x5 = 10 subject to each xi is a non-negative integer. If we want each xi to be
at least 1, write xi = yi + 1 where now each yi is a non-negative integer. This leads to the equation y1 + y2 + y3 + y4 + y5 =
5, and the answer is just (5 + 4 choose 4). If we want just x1 to be at least 3 (as that’s the professor) and all others to be
at least zero, let x1 = z1 + 3 and xi = zi for i in {2,3,4,5}; this gives z1 + z2 + z3 + z4 + z5 = 7, or (7 + 4 choose 4). It
is VERY hard to put in upper bounds, ie, force a given person to have AT MOST a fixed number of cookies; I can only do this in
large limit cases via the central limit theorem. If anyone knows a good way, please drop me an email at sjm1 AT williams.edu.
4/ A related problem is the following: Say you have a lottery with 40 numbers and you have to choose 6 where the ORDER
doesn’t matter, no repeats. The answer is just (40 choose 6). What if you ARE allowed to reuse numbers? All that matters is
that you get the right numbers, not the order. How many combinations are there now?
5/ I liked the recurrence relation approach. It should be possible to combine that with induction to get the formula in
general.
6/ Another generalization related to this is asking how many ways are there to divide C cookies among P people where you DO NOT
have to give out all the cookies! There’s a very nice one line solution to this.
General comment: I love the combinatorial perspective this offers. I’ve used this in at least two papers. One is on closed form Bayesian
inferences, the other is on writing numbers
as sums of non-consecutive Fibonacci numbers (the Zeckendorf decomposition) and Gaussian behavior.