C is for Cookie
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?
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?
450? I got this because I think: Each child has 90 possibilities (10,1;10,2; ect) and there are five children. So 90*5=450
No, not quite right. Each child has 11 possibilities, ranging from 0 to 11. If they were all independent, the answer would be 11^5. Unfortunately, they’re not independent, which is what makes this problem hard. For example, if I have 8 cookies, no one can have more than 2. Further, the number of cookies must sum to 10. There *IS* a way to do this in one line, if you can find the right way to look at the problem. This is one of my favorite riddles, and is related to some great problems in additive number theory and combinatorics.
I got 225, because I found that each child had 45 possibilities. 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 1,10 2,3 2,4 2,5 2,6 2,7 2,8 2,9 2,10 3,4 3,5 3,6 3,7 3,8 3,9 3,10 4,5 4,6 4,7 4,8 4,9 4,10 5,6 5,7 5,8 5,9 5,10 6,7 6,8 6,9 6,10 7,8 7,9 7,10 8,9 8,10 9,10
I multiplied 45 times the 5 children.
Or…wait…should I do 45^5????????
This isn’t quite right. Not sure how you’re getting the 45 possibililties for each child. Each child has 11 possibilities, from 0 to 10; however, the children are not independent (if one has 9 the others can have at most 1). If you want more hints / info, email me at sjm1 AT williams.edu.
Yair.K: great logic, absolutely correct. Not posting it as it gives the solution.
Number the cookies from 1 to 10. Lay them down in a roll:
1,2,3,4,5,6,7,8,9,10
Pretend that there are 4 barriers that you can place anywhere in between 2 of these cookies or the beginning of the roll or the end of the cookie roll so that what ever to the left of the i-th barrier will be distributed to the i-th kid. And the remaining cookies would be distributed to the last kid.
There are 11 spaces to place the barriers and there are 4 barries to place so 11^4 total possible combinations.
you’re on the right track
but what if you put two dividers next to each other?
Could it be 11 x 10 x 9 = 990? Since each child can have 0 – 10 cookies, so each child has 11 different number of cookies to get?
The answer is 50. Assume that there are ten separate events occurring. Each event is the exact same as all the others. The event is defined by 1 cookie being thrown into a group of five kids. Each event has 5 possible arrangements (the cookies could go to only one of the five kids). Since there are ten events, with 5 possible arrangements for each event, then there are 10(5) total arrangements. This yields 50 total possible arrangements.
Not quite. You’ve made two errors. Remember that if I get cookies 1 and 2 or cookies 4 and 10, I can’t tell the difference. What you’ve done has the cookies as distinct and labeled. IF you were to take this approach, the final answer would be 5^10, though, and not 5*10.
Doing this on a cookie by cookie basis, number the cookies 1 to 10. For each cookie there are only 5 choices and since the cookie has to go to somebody, there are 5 ways to hand out the first cookie. This is the case for a single cookie. For the second cookie, you again have 5 choices for whom to give it to, so n=2 gives 5² ways to distribute the cookies. For 10 cookies then there are 5^10 ways to distribute them, and for n cookies there are 5^n ways to distribute them.
*IF* the cookies were distinguishable, yes, this would be the solution; however, at the end of the day you can’t tell WHICH cookies you have, only how many.
If it does require each kid must have a cookie then it’s 1001.
That’s the right answer, but each kid doesn’t have to have a cookie.
If we line the cookies up in a row and use 4 dividers to split the cookies up into 5 groups we can determine the number of cookies for each kid. I split the possibilities into 5 cases and solved each. The first case is that all 4 dividers are separate (11!/(7!4!)). The second case is that 2 of the dividers are together (11!/8!). The third case is that there are 2 sets of 2 dividers (11!/(9!2!)). The fourth case is a set of 3 dividers together and a third by itself (11!/9!). The fifth and final case is having all the dividers together or (11!/10!). After summing the 5 cases I get 1496 possibilities. Is this correct?
you’re on the right track, but overanalyzing
just look at how many ways you can place divisors. it’s easier to add some
cookies and eat them, thus creating divisors. how many cookies to add…?
I am trying to do this with 6th graders and am having a hard time getting them interested. Is there a way I can start them off on the right track without giving them the answer. I think I took on more than either I or the students can handle but don’t want to give up on this. Ideas??
Is the problem keeping them interested, or starting the problem?
One way to make it interesting is to bring in cookies.
One thing I’d love to do is fine applications for various riddles. If you’re interested in helping
that would be great — I’m swamped now but am trying to assemble a team, where each person would
take / research one riddle.
It turns out the answer is a binomial coefficient, and a very interesting one too. Maybe give that
as a hint, do some smaller numbers of cookies and people and see if you can ‘guess’ the answer.
math related to this is used to calculate the number of winning lottery tickets *IF* you can use
the same numbers again and again. It’s also used to study some problems in Diophantine analysis /
number theory. What we’re really doing is trying to solve x_1 + … + x_5 = 10 subject to each x_i
is a non-negative integer. In other words, trying to decompose a big number into smaller ones, and
interested in how many ways there are to do this. This has applications to physics / statistical
mechanics!
I think the answer is 1331 which is 11 x 11 x 11 x 11. Am i right? If not please email the hint to me.
Not quite. It’s almost 300 left. Your method seems to double count. Remember that each person only cares how many cookies they get, not which ones. If you know binomial coefficients, think partitions….
that’s a little high — I have slightly above 1000.
Personal: correct! not posting as it’s the soln
Well, I assume the answer is simple. You just have to check the number of possibilities you may distribute the cookies to each… So, if the number of cookies is 10 and five kids, the answer is 10x9x8x7x6=30240
It’s a bit harder and more complicated than that — email me at sjm1@williams.edu if you want a hint
Well… if A can receive from 0 to 10 cookies… there are 11 possibilities for that child. Each child has at least 11 possibilities. If there are 5 children… then it looks like it would just be 11^5. That seems too simple though… hmm… I can’t think of anything else.
all that matters is how many cookies one gets, not which cookies. 11^5 is wrong. you might try 5^10, as each cookie is assigned to one of 5 people, but the issue there is that this makes each cookie ‘special’ or ‘distinguishable’. email me at sjm1@williams.edu if you want more of a hint.
to Lee: correct, well done! Not posting this as it’s the soln.
sadly your brain needs more time in the oven, as it isn’t quite cooked enough! let me know if you want a hint.
It’s not a permutation, but there is a combinatorial interpretation. /s/
Is it just 1 because all the cookies are identical?
Sorry if this is a stupid comment…
no. we could give all the cookies to one person (5 ways of doign this), or 9 cookies to 1 person and 1 to another (20 ways of doing this), …. There is a better approach.
I got 971. Here’s my reasoning…
I worked out the combinations for 1 cookie up to four cookies by hand and categorized them by the first cookie recipient. For example, with 1 cookies, “20000” goes in category 1, while “02000” goes in category 2. The digits represent how many cookies went to each kid.
1 Cookie – 1 + 1 + 1 + 1 + 1 = 5 combinations.
2 Cookies – 5 + 4 + 3 + 2 + 1 = 15 combinations
3 Cookies – 15 + 10 + 6 + 3 + 1 = 35 combinations
4 Cookies – 35 + 20 + 10 + 4 + 1 = 70 combinations
Here I noticed a pattern. The number of combinations in the previous cookie # was the number of combinations in the next cookie #’s first category. The last category always had 1. The second category rose by 1’s. The 3rd category rose by whatever is in the 2nd, the 4th by whatever is in the 3rd, and the 5th by whatever is in the 4th.
I tested the pattern with 5 cookies, and it worked. I went ahead and went up to 10 cookies.
5 Cookies – 70 + 35 + 15 + 5 + 1 = 126
6 Cookies – 126 + 56 + 21 + 6 + 1 = 210
7 Cookies – 210 + 84 + 28 + 7 + 1 = 330
8 Cookies – 330 + 110 + 36 + 8 + 1 = 485
9 Cookies – 485 + 155 + 45 + 9 + 1 = 695
10 Cookies – 695 + 210 + 55 + 10 + 1 = 971
I’m confused as to how the answer is [[deleted]] combinations. If you could email me the solution, thatd be great.
I’m not following all of your logic as to how you get these numbers. I’ll send my soln. //s
Sorry, a bit too low. Email me at sjm1 AT williams.edu to chat more. //s
I took all possibilities for one kid and it gave me 5*9+5*8+…+5*1=225
Then I multiplied that by the number of kids and I got 1125. Pretty close but something doesn’t feel right I guess 😛
I’m not seeing how this is the number for each kid, nor why you can just multiply by 5 (there’s a big danger of double counting). You’re close (within 200). Email me at sjm1 AT williams.edu if you want the soln / hint.
shouldnt the possible amount per kid be 10, not 11? Teh problem says teh cookies will be given to 5 students, if you skip a student (ie a zero) than you would be using four students in some counts and five in others. If you use 11 as the number than you arent really giving cookie/s to all children
you can consider a modified problem where each kid must get at least one cookie. you get a different answer in that case, but the same ‘fast’ technique works there too….
What if instead I said we had to distribute 4 cookies among 5 people? Then there’s no way everyone gets one. That said, the answer isn’t 525 in any of these interpretations. I’ll send along my answer. //s
I come up with the following, what am I missing?
(10,0) = 5
(9,1) 5×4 = 20
(8,2) 5×4 = 20
(8,1,1) 5x(3+2+1) = 30
(7,3) 5×4 = 20
(7,2,1) 5x4x3 = 60
(7,1,1,1) 5×4 = 20
(6,4) 5×4 = 20
(6,3,1) 5x4x3 = 60
(6,2,2) 5x(3+2+1) = 30
(6,2,1,1) 5x4x3 = 60
(6,1,1,1,1) = 5
(5,5) 4+3+2+1 = 10
(5,4,1) 5x4x3 = 60
(5,3,2) 5x4x3 = 60
(5,3,1,1) 5x4x3 = 60
(5,2,2,1) 5x4x3 = 60
(5,2,1,1,1) 5×4 = 20
(4,4,2) 5x(3+2+1) = 30
(4,4,1,1) (4+3+2+1)x3 = 30
(4,3,3) 5x(3+2+1) = 30
(4,3,2,1) 5x4x3x2 = 120
(4,3,1,1,1) 5×4 = 20
(4,2,2,2) 5×4 = 20
(4,2,2,1,1) 5x(3+2+1) = 30
(3,3,3,1) 5×4 = 20
(3,3,2,1,1) 5x(3+2+1) = 30
(2,2,2,2,2) = 1
+
951
VERY close, but as often happens in problems like this is you missed a few cases. There’s a way to look at this in one line, and that gives the answer. I solved it that way, and unfortunately this means I don’t know the counts for the different configurations, so I can’t tell where you went wrong. Email me at sjm1 AT williams.edu for the soln.
close, but not quite right. email me at sjm1 AT williams.edu if you want to chat /s
you’re on the right track, but it’s not 10C5 = 252
email me at sjm1 AT williams.edu to chat more
Can you send me the solution and explain it to me pls?, my brain is tired 🙁
amel: correct, well done — you can email me at sjm1 AT williams.edu to chat about it. ..s
I have read every comment and I have tried to solve this, please send solution. Thanks.
Is it 5^10? Each cookie has 5 potential “places” it could go…
no — all that matters is how many cookies a person gets, not which cookies someone gets. if that were the case, then yes, it would be 5^10.
your email didn’t work — email me at sjm1 AT williams.edu — wrong answer here
2^10. i think years ago my teacher told me if you want to make combination with for example X numbers then the answer is 2^X.
if its not right email me a hint.
cheers
that would be the soln of the number of ways to give cookies to ONE person IF the cookies were distinguishable. If the cookies are distinguishable it’s 5^10; hwoever, the cookies are all identical; all that matters is how many one receives, not which ones. (sjm1 AT williams.edu)
reminds me another puzzle. you have 20 basketball players and you are asked to find in how many different ways you can divide them in four teams of five players each. are the solutions similar?? please send me a hint or the solution for both as i cant seem to figure out anything. thanks.
If you want a response to your comments you must leave a valid email address. Failure to leave a valid email address may result in your post being ignored. The reason is all posts are moderated to make sure nothing is posted that will give away the solution to someone who does not wish to see it.
Comments
Leave a comment