Here are thoughts about C is for Cookie. These notes are meant to help you not only solve the problem, but other problems as well. Thus there are a lot of comments on why we try certain things, and a lot of related questions and calculations are deliberately left for you to do and ponder. At the end is a short summary, including a list of important techniques and methods that appear in the problem, and some further reading.

First, let’s review the statement:

Problem: Ten identical cookies are to be distributed among five different kids (A, B, C, D, and E). All 10 cookies are distributed. How many different ways can the five kids be given cookies?

First thoughts: We start by looking for the key words. The cookies are identical; this means we cannot tell one cookie from another. However, the kids are all different, so we can tell one kid from another. If the cookies and the kids were distinguishable, the problem would be a lot easier. In this case, there are 5^10 possibilities. Why? Each cookie is assigned to one of five students. Thus there are five choices for the assignment of the first cookie, five for the second, five for the third and so on. We multiple the possibilities, and get 5 * 5 * 5 * 5 * 5 * 5 *5 * 5 *5 * 5 or 9,765,625.

This can’t be the right answer, though, as all the cookies are identical. The approach above doesn’t distinguish between the first person getting just cookie 2 and the first person getting just cookie 7. We need to refine our analysis and take into account the fact that the cookies are identical.

We could solve this problem by enumerating all the possible cases, but this isn’t fun (and it’s not enlightening either). For example, A gets 10 and the rest 0, then B gets 10 and the rest 0 and so on. We can save time by writing these as tuples: (10,0,0,0,0), (0,10,0,0,0); after doing all the cases of someone getting 10 we do the case when the most someone gets is 9. There were 5 cases when the maximum someone got was 10; now there are 20 cases! Here’s the first few: (9,1,0,0,0), (9, 0,1,0,0), (9,0,0,1,0), (9,0,0,0,1), (9,0,0,0,1), (1,9,0,0,0), (0,9,1,0,0), (0,9,0,1,0), (0,9,0,0,1), (1,0,9,0,0), …. You need to be careful not to miss any case, so it’s worth thinking of a good way to go through the cases. Also, as bad as this is, think about the case when the maximum someone gets is 4! We clearly need a better way. As this is a riddle, there almost surely is a better way, and one that will introduce us to some great ideas in mathematics.

Second thoughts: Good advice is always to consider simpler cases. Instead of looking at 10 cookies and 5 people, perhaps we should try smaller numbers and see if we can detect a pattern. The general problem is C identical cookies and P distinct people. We can go through different choices of C and P and tabulate the answer, and try to guess the form of the solution f(C,P). Notice we’ve introduced a function to represent the answer. Our function f depends on two parameters; the first is the number of identical cookies, while the second is the number of distinct people.

Let’s start with P = 1. This is particularly easy: all the cookies must go to that person, and thus f(C,1) = 1 for any C.

Now let’s try our luck with P  = 2. This case is a bit harder and a bit more interesting. Once we assign some number of cookies to the first person, the second person must get all the cookies that are left. The possibilities are the first person gets 0 cookies, or 1 cookie, or 2 cookies, …, or C cookies. Thus there are C+1 assignments, and f(C,2) = C+1.

We’ve made some progress. We know f(C,1) = 1 and f(C,2) = C+1. Unfortunately this is not enough information to make a good conjecture; there are too many possibilities. As a nice exercise, try and figure out some of these possibilities, and try to guess what f(C,3) might be.

How should we do P=3? One possibility is to take some small values of C and just grind through the possibilities. I urge you to try this, and see if a pattern emerges. There is another option here, and this approach introduces us to one of the most important techniques in mathematics: reduce a problem to a simpler one. Mathematicians are lazy; let’s not re-invent the wheel. Try to convert a new problem to one you’ve solved. Let’s think about what’s going on. We have three people and C cookies. The first person gets some number of cookies; let’s say they get k cookies and k can be any number from 0 to C. This leaves C-k cookies for the other two people. Ahh, but we know how many ways there are to divide C-k cookies among 2 people; this is just f(C-k,2) which is C-k+1. The solution is just adding these for each choice of k. Thus the answer is f(C,3) = Sum_{k = 0 to C} f(C-k,2); this summation notation means f(C-0,2) + f(C-1,2) + f(C-2,2) + … + f(C-C,2). We made one person `special’, and then after giving them their cookies we were left with a simpler problem. This is great progress, and now we are left with executing this sum.

What is the sum? It might be easiest to put in specific values of C and try to guess the form — this is another good exercise for you to try. I’m going to jump to the answer. Since f(C-k,2) = C-k+1, we find f(C,3) = f(C-0,2) + f(C-1, 2) + … + f(C-C,2) = (C-0+1) + (C-1+1) + (C-2+1) + (C-3+1) + … + (C-C+1), but this is just (C+1) + (C) + (C-1) + (C-2) + … + (1). In other words, we have the sum of the first C+1 numbers. There are many ways to figure out this sum. While mathematical induction is a nice one, I particularly enjoy the following trick. If we let x equal this sum, notice that 2x is  (C+1) + (C) + (C-1) + (C-2) + … + (1) plus (1) + (2) + … + (C-1) + (C) + (C+1) (where we just wrote the sum in reverse order, which won’t change its value). Now it’s easy to add. The sum of the two first terms is C+2, as is the sum of the two second terms, and the two third terms, and so on. We have C+1 terms, so we find 2x = (C+1)(C+2), so x = (C+1)(C+2)/2. Thus f(C,3) = (C+1)(C+2)/2.

We could go through and figure out the case when P=4. If we did this, we would get f(C,4) = SUM_{k = 0 to C} f(C,3), and we would find a cubic in C. This is another good case for you to work out explicitly, and see if you can find the pattern. Or, if you are just interested in solving the problem, you can now find f(C,4) and then from this get f(10,5) by noting f(10,5) = Sum_{k = 0 to 10} f(10-k, 4).

Third thoughts: Let’s try and find the pattern. We record what we know: f(C,1) = 1, f(C,2) = C+1, f(C,3) = (C+1)(C+2)/2. If we really worked hard and did P=4, we’d find f(C,4) = (C+1)(c+2)(c+3)/6. This is where experience helps. The 6 in the denominator can be written as 3!, and the 2 in the denominator of f(C,3) could be 2!; here n! is n*(n-1)*(n-2)*…*3*2*1. We read n! as n factorial; it is the number of ways to order n objects when order matters. In fact, we could even write f(C,2) as (C+1)/1!. If we do this, we can interpret our answers as f(C,1) = 1, f(C,2) = (C+1)/1!, f(C,3) = (C+1)(C+2)/2!, and f(C,4) = (C+1)(C+2)(C+3)/3!. This suggests that the answer might be f(C,P) = (C+1)(C+2)*…*(C+P-1) / (P-1)! (we have to be a bit careful about interpreting this when P=1; in this case the denominator is 0! and the convention is that equals 1, while the numerator is an empty product since the last term is earlier than the first, and the convention here is that an empty product is 1).

It turns out this guess is correct — the answer really is f(C,P) = (C+1)(C+2)*…*(C+P-1) / (P-1)!. There’s a very nice way to write our guess. The binomial coefficient nCk (read n choose k) is nCk = (n choose k) = n! / (k! (n-k)!); it is the number of ways to choose k objects from n objects when order does not matter. We now employ another wonderful method in mathematics. We multiply by 1. Multiply by 1 is one of the most important methods to master — it is not easy to learn how to do nothing well! Here we multiply by 1 in the following form: 1 = C! / C!. Using this, we may rewrite our guess as (C+1)(C+2)*…*(C+P-1) / (P-1)! as f(C,P) = [C! * (C+1)(C+2)*…*(C+P-1)] / [(P-1)! C!]. Notice the top is just (C+P-1)!, and therefore our guess is (C+P-1)! / ((P-1)! C!), which is just (C+P-1 choose P-1).

Again, we haven’t proved that this is the answer, but we have strong evidence that f(C,P) might be (C+P-1 choose P-1). Having a good guess is a wonderful start towards the solution. Often the functional form of the answer gives a clue as to how it is proved. Since this is a binomial coefficient, there is a combinatorial interpretation; it is the number of ways of choosing P-1 objects from C+P-1 objects. It’s not surprising that the answer is combinatorial, as this is a combinatorics problem. The question now is: given the hint that we need to choose P-1 objects from C+P-1 objects, how can find this in the solution? In other words, how do we show that the number of valid, distinct assignments (where all that matters is how many cookies each person gets) is (C+P-1 choose P-1)? Try to think about how you might get this before reading on.

Fourth thoughts: We are trying to find a (C+P-1 choose P-1) in our problem. Let’s revisit what we have: we have C cookies and P people. Thus it would be natural to expect something like (C choose P) to surface, but this can’t be the solution. It doesn’t match the cases we’ve already solved, and it has the wrong interpretation — it’s selecting P of C cookies.

Final Comments: We saw a lot of nice techniques in this problem, as well as suggestions of other related ones. We saw the power of doing some small cases to find a pattern. We needed to find the sum of the first C+1 integers; while we could’ve done this by induction there was a nice matching trick that helped (I find it amusing that it’s easier to find 2x than x; this is fine as it’s easy to divide by 2). We then saw how to interpret our guess — the fact that it was a binomial coefficient was a great hint at how to look at the problem. The last step was the hardest. If we only cared about the solution we could use our recursive approach: we can solve for f(C,P) knowing f(C,P-1) and thus pull up our answers. This is better than brute force, but still requires some work. Our final solutions is a one line calculation, which is very nice.

This is called the Stars and Bars problems by many (see the wikipedia entry here); I call it the Cookie Problem because of this riddle.

Wikipedia has a nice article on mathematical induction. The sums of the first n integers give the n-th triangular number; there are generalized formulas for sums of powers.

It’s also worthwhile looking up binomial coefficients, which you might have seen in Pascal’s triangle. This set has many wondrous properties. One nice one emerges when you look at the numbers in Pascal’s triangle modulo 2. This means we replace all the odd numbers with 1 and all the even numbers with 0, or equivalently color black all the odd numbers and white all the evens. A fractal pattern emerges! There are many applications of fractals, and I find it nice to see them emerge from something you’ve hopefully seen before, but are now seeing in a new light.

I’ve used the cookie problem in some of my research. See this paper on Zeckendorf decompositions and Gaussian behavior (done with several students at the Williams College summer mathematics research program for undergraduates).

Finally, whenever you solve a problem you should pause and celebrate. Enjoy the moment, but then move on. Can you generalize? Can you tweak the problem? Here all the cookies had to be divided among the people. What if this is not true? What if now we have 10 identical cookies and 5 distinct people, and we divide some number among the people, only caring about how many each kid gets. It turns out that, if you view the problem properly, this too can be solved in one line. This is yet another example of a powerful principle in combinatorics: if you look at the problem the right way, it’s often `relatively’ easy to reach the answer. The answer in this case is another binomial coefficient — happy hunting!

Here are thoughts about C is for Cookie. These notes are meant to help you not only solve the problem, but other problems as well. Thus there are a lot of comments on why we try certain things, and a lot of related questions and calculations are deliberately left for you to do and ponder. At the end is a short summary, including a list of important techniques and methods that appear in the problem, and some further reading.

First, let’s review the statement:

Problem: Ten identical cookies are to be distributed among five different kids (A, B, C, D, and E). All 10 cookies are distributed. How many different ways can the five kids be given cookies?

First thoughts: We start by looking for the key words. The cookies are identical; this means we cannot tell one cookie from another. However, the kids are all different, so we can tell one kid from another. If the cookies and the kids were distinguishable, the problem would be a lot easier. In this case, there are 5^10 possibilities. Why? Each cookie is assigned to one of five students. Thus there are five choices for the assignment of the first cookie, five for the second, five for the third and so on. We multiple the possibilities, and get 5 * 5 * 5 * 5 * 5 * 5 *5 * 5 *5 * 5 or 9,765,625.

This can’t be the right answer, though, as all the cookies are identical. The approach above doesn’t distinguish between the first person getting just cookie 2 and the first person getting just cookie 7. We need to refine our analysis and take into account the fact that the cookies are identical.

We could solve this problem by enumerating all the possible cases, but this isn’t fun (and it’s not enlightening either). For example, A gets 10 and the rest 0, then B gets 10 and the rest 0 and so on. We can save time by writing these as tuples: (10,0,0,0,0), (0,10,0,0,0); after doing all the cases of someone getting 10 we do the case when the most someone gets is 9. There were 5 cases when the maximum someone got was 10; now there are 20 cases! Here’s the first few: (9,1,0,0,0), (9, 0,1,0,0), (9,0,0,1,0), (9,0,0,0,1), (9,0,0,0,1), (1,9,0,0,0), (0,9,1,0,0), (0,9,0,1,0), (0,9,0,0,1), (1,0,9,0,0), …. You need to be careful not to miss any case, so it’s worth thinking of a good way to go through the cases. Also, as bad as this is, think about the case when the maximum someone gets is 4! We clearly need a better way. As this is a riddle, there almost surely is a better way, and one that will introduce us to some great ideas in mathematics.

Second thoughts: Good advice is always to consider simpler cases. Instead of looking at 10 cookies and 5 people, perhaps we should try smaller numbers and see if we can detect a pattern. The general problem is C identical cookies and P distinct people. We can go through different choices of C and P and tabulate the answer, and try to guess the form of the solution f(C,P). Notice we’ve introduced a function to represent the answer. Our function f depends on two parameters; the first is the number of identical cookies, while the second is the number of distinct people.

Let’s start with P = 1. This is particularly easy: all the cookies must go to that person, and thus f(C,1) = 1 for any C.

Now let’s try our luck with P  = 2. This case is a bit harder and a bit more interesting. Once we assign some number of cookies to the first person, the second person must get all the cookies that are left. The possibilities are the first person gets 0 cookies, or 1 cookie, or 2 cookies, …, or C cookies. Thus there are C+1 assignments, and f(C,2) = C+1.

We’ve made some progress. We know f(C,1) = 1 and f(C,2) = C+1. Unfortunately this is not enough information to make a good conjecture; there are too many possibilities. As a nice exercise, try and figure out some of these possibilities, and try to guess what f(C,3) might be.

How should we do P=3? One possibility is to take some small values of C and just grind through the possibilities. I urge you to try this, and see if a pattern emerges. There is another option here, and this approach introduces us to one of the most important techniques in mathematics: reduce a problem to a simpler one. Mathematicians are lazy; let’s not re-invent the wheel. Try to convert a new problem to one you’ve solved. Let’s think about what’s going on. We have three people and C cookies. The first person gets some number of cookies; let’s say they get k cookies and k can be any number from 0 to C. This leaves C-k cookies for the other two people. Ahh, but we know how many ways there are to divide C-k cookies among 2 people; this is just f(C-k,2) which is C-k+1. The solution is just adding these for each choice of k. Thus the answer is f(C,3) = Sum_{k = 0 to C} f(C-k,2); this summation notation means f(C-0,2) + f(C-1,2) + f(C-2,2) + … + f(C-C,2). We made one person `special’, and then after giving them their cookies we were left with a simpler problem. This is great progress, and now we are left with executing this sum.

What is the sum? It might be easiest to put in specific values of C and try to guess the form — this is another good exercise for you to try. I’m going to jump to the answer. Since f(C-k,2) = C-k+1, we find f(C,3) = f(C-0,2) + f(C-1, 2) + … + f(C-C,2) = (C-0+1) + (C-1+1) + (C-2+1) + (C-3+1) + … + (C-C+1), but this is just (C+1) + (C) + (C-1) + (C-2) + … + (1). In other words, we have the sum of the first C+1 numbers. There are many ways to figure out this sum. While mathematical induction is a nice one, I particularly enjoy the following trick. If we let x equal this sum, notice that 2x is  (C+1) + (C) + (C-1) + (C-2) + … + (1) plus (1) + (2) + … + (C-1) + (C) + (C+1) (where we just wrote the sum in reverse order, which won’t change its value). Now it’s easy to add. The sum of the two first terms is C+2, as is the sum of the two second terms, and the two third terms, and so on. We have C+1 terms, so we find 2x = (C+1)(C+2), so x = (C+1)(C+2)/2. Thus f(C,3) = (C+1)(C+2)/2.

We could go through and figure out the case when P=4. If we did this, we would get f(C,4) = SUM_{k = 0 to C} f(C,3), and we would find a cubic in C. This is another good case for you to work out explicitly, and see if you can find the pattern. Or, if you are just interested in solving the problem, you can now find f(C,4) and then from this get f(10,5) by noting f(10,5) = Sum_{k = 0 to 10} f(10-k, 4).

Third thoughts: Let’s try and find the pattern. We record what we know: f(C,1) = 1, f(C,2) = C+1, f(C,3) = (C+1)(C+2)/2. If we really worked hard and did P=4, we’d find f(C,4) = (C+1)(c+2)(c+3)/6. This is where experience helps. The 6 in the denominator can be written as 3!, and the 2 in the denominator of f(C,3) could be 2!; here n! is n*(n-1)*(n-2)*…*3*2*1. We read n! as n factorial; it is the number of ways to order n objects when order matters. In fact, we could even write f(C,2) as (C+1)/1!. If we do this, we can interpret our answers as f(C,1) = 1, f(C,2) = (C+1)/1!, f(C,3) = (C+1)(C+2)/2!, and f(C,4) = (C+1)(C+2)(C+3)/3!. This suggests that the answer might be f(C,P) = (C+1)(C+2)*…*(C+P-1) / (P-1)! (we have to be a bit careful about interpreting this when P=1; in this case the denominator is 0! and the convention is that equals 1, while the numerator is an empty product since the last term is earlier than the first, and the convention here is that an empty product is 1).

It turns out this guess is correct — the answer really is f(C,P) = (C+1)(C+2)*…*(C+P-1) / (P-1)!. There’s a very nice way to write our guess. The binomial coefficient nCk (read n choose k) is nCk = (n choose k) = n! / (k! (n-k)!); it is the number of ways to choose k objects from n objects when order does not matter. We now employ another wonderful method in mathematics. We multiply by 1. Multiply by 1 is one of the most important methods to master — it is not easy to learn how to do nothing well! Here we multiply by 1 in the following form: 1 = C! / C!. Using this, we may rewrite our guess as (C+1)(C+2)*…*(C+P-1) / (P-1)! as f(C,P) = [C! * (C+1)(C+2)*…*(C+P-1)] / [(P-1)! C!]. Notice the top is just (C+P-1)!, and therefore our guess is (C+P-1)! / ((P-1)! C!), which is just (C+P-1 choose P-1).

Again, we haven’t proved that this is the answer, but we have strong evidence that f(C,P) might be (C+P-1 choose P-1). Having a good guess is a wonderful start towards the solution. Often the functional form of the answer gives a clue as to how it is proved. Since this is a binomial coefficient, there is a combinatorial interpretation; it is the number of ways of choosing P-1 objects from C+P-1 objects. It’s not surprising that the answer is combinatorial, as this is a combinatorics problem. The question now is: given the hint that we need to choose P-1 objects from C+P-1 objects, how can find this in the solution? In other words, how do we show that the number of valid, distinct assignments (where all that matters is how many cookies each person gets) is (C+P-1 choose P-1)? Try to think about how you might get this before reading on.

Fourth thoughts: We are trying to find a (C+P-1 choose P-1) in our problem. Let’s revisit what we have: we have C cookies and P people. Thus it would be natural to expect something like (C choose P) to surface, but this can’t be the solution. It doesn’t match the cases we’ve already solved, and it has the wrong interpretation — it’s selecting P of C cookies.

Final Comments: We saw a lot of nice techniques in this problem, as well as suggestions of other related ones. We saw the power of doing some small cases to find a pattern. We needed to find the sum of the first C+1 integers; while we could’ve done this by induction there was a nice matching trick that helped (I find it amusing that it’s easier to find 2x than x; this is fine as it’s easy to divide by 2). We then saw how to interpret our guess — the fact that it was a binomial coefficient was a great hint at how to look at the problem. The last step was the hardest. If we only cared about the solution we could use our recursive approach: we can solve for f(C,P) knowing f(C,P-1) and thus pull up our answers. This is better than brute force, but still requires some work. Our final solutions is a one line calculation, which is very nice.

This is called the Stars and Bars problems by many (see the wikipedia entry here); I call it the Cookie Problem because of this riddle.

Wikipedia has a nice article on mathematical induction. The sums of the first n integers give the n-th triangular number; there are generalized formulas for sums of powers.

It’s also worthwhile looking up binomial coefficients, which you might have seen in Pascal’s triangle. This set has many wondrous properties. One nice one emerges when you look at the numbers in Pascal’s triangle modulo 2. This means we replace all the odd numbers with 1 and all the even numbers with 0, or equivalently color black all the odd numbers and white all the evens. A fractal pattern emerges! There are many applications of fractals, and I find it nice to see them emerge from something you’ve hopefully seen before, but are now seeing in a new light.

I’ve used the cookie problem in some of my research. See this paper on Zeckendorf decompositions and Gaussian behavior (done with several students at the Williams College summer mathematics research program for undergraduates).

Finally, whenever you solve a problem you should pause and celebrate. Enjoy the moment, but then move on. Can you generalize? Can you tweak the problem? Here all the cookies had to be divided among the people. What if this is not true? What if now we have 10 identical cookies and 5 distinct people, and we divide some number among the people, only caring about how many each kid gets. It turns out that, if you view the problem properly, this too can be solved in one line. This is yet another example of a powerful principle in combinatorics: if you look at the problem the right way, it’s often `relatively’ easy to reach the answer. The answer in this case is another binomial coefficient — happy hunting!

Final Thoughts: For those who kept reading, here’s your reward, a brute force solution! The solutions are represented as tuples of six numbers. The first five represent how many cookies go to person A, B, C, D and E; the sixth number represents all the different ways we can rearrange those numbers. For example, there are 5 ways to give 10 cookies to one person. There are 20 ways to give 9 cookies to one person and 1 to another. These rearrangement countings can be obtained by brute force, as well as combinatorics (when using binomial coefficients to find these rearrangements, remember there is a big difference between two distinct numbers and two identical numbers).

0 0 0 0 10 5

0 0 0 1 9 20
0 0 0 2 8 20
0 0 0 3 7 20
0 0 0 4 6 20
0 0 0 5 5 10

0 0 1 1 8 30
0 0 1 2 7 60
0 0 1 3 6 60
0 0 1 4 5 60
0 0 2 2 6 30
0 0 2 3 5 60
0 0 2 4 4 30
0 0 3 3 4 30

0 1 1 1 7 20

0 1 1 2 6 60
0 1 1 3 5 60
0 1 1 4 4 30
0 1 2 2 5 60
0 1 2 3 4 120
0 1 3 3 3 20
0 2 2 2 4 20
0 2 2 3 3 30

1 1 1 1 6 5
1 1 1 2 5 20
1 1 1 3 4 20
1 1 2 2 4 30
1 1 2 3 3 30
1 2 2 2 3 20

2 2 2 2 2 1
TOTAL 1001

Consider the set {1,11,111, …, ((10^2007) – 1)/9}.

Don’t hold your horses — race them!

How can you guess that?

Is this seat taken?

What’s my card?