Allow me to introduce you to combinatorics, the mathematics of counting (skip ahead to the puzzle if you already know it). You all know how to count, right? Yeah, me neither. But combinatorics is a bit different from what you might expect. Let's say I have a class of twenty students, and I want to put three of them in a group. How many different ways are there to do this?
To pick the first student in the group, you have 20 choices. For the second you have 19. For the third, you have 18. That gives 20*19*18 = 20!/17! choices.* But some of these choices have been overcounted, because you could have chosen the same three students in a different order. Therefore, we must divide by 3*2*1=3!, which is the number of different ways to order three students.
*If you're not familiar with it, ! is the factorial function. For example 5!, or "five factorial" is 5*4*3*2*1=120.
The final result is called the "choose function", which is written below:
The puzzle: Candy giveaway
Let's say that I have five pieces of candy to give out to my twenty students. How many different ways are there to distribute all the candy? All the pieces of candy are identical, so it doesn't matter which candies the students get, just how much candy they each get.
Hint! I introduced the choose function for a reason. The answer is a choose function, but it's not C(20,5). Bonus points for deriving the general formula for N students and K pieces of candy.
Believe it or not, this problem has applications in physics. It's used in boson statistics, because like the candy, bosons are identical. This is what leads to blackbody radiation and Bose-Einstein condensates. The day I learned this was the day I fell in love with physics, or it would have been if I didn't already love physics by then.
Bonus problem: Class Candy Clash
Here's a puzzle for those people who already knew the previous one. Let's say that I teach a class of twenty students, and my colleague simultaneously teaches another class of twenty. We want to organize a competition, my class against hers. The winning class will get all the candy. All of it.
I will pick a group of students from my class to be my class's team. She will do the same. Naturally, each team must be the same size. How many ways are there for the two of us to pick teams?
solutions posted
Perhaps I misunderstood the Q. Are you bound to give out all of the candy to your students? If so, and presuming that you could choose to give a student more than one piece (or all of them), isn't the answer just 20^5 since each piece of candy can be allocated to 1 of 20 "positions"?
ReplyDeleteNo, you're over counting. Remember that each piece of candy is identical. For example, if you give one candy to student A and one candy to student B, it doesn't matter which candy is which. All that matters is that A and B each got one candy.
ReplyDeleteHow about N^k / k! for the first?
ReplyDeleteFor the second I presume you're looking for the number of combinations of teams between the two of you; ie you can pick 20 different 1-person teams and so can your colleague for a total of 20^2=400 variations.
Two-person teams would be 190^2, 3-person 1,140^2, and so on.
I get a little over 10^12 different ways of choosing teams of from 1 to 20 members from classes of 20.
Nope, not correct. N^k/k! isn't even necessarily an integer.
ReplyDeleteFor the bonus problem, you can simplify to a choose function.
Ok, my fault for trying to get a quick answer before bed. It's after midnight again here but the answer I have now seems to make more sense.
ReplyDeleteI think we need to add some "ghost" students for when you give candy to a student who already has some. So in your example we need 4 ghost students.
General formula is C(N+k-1, k) or
(N+k-1)!/(N-1)!k!
Interesting that the answers are related to triangular numbers of the same dimension number as the number of pieces of candy; ie the answer to your stated problem is the 20th 5-D hyper-tetrahedral number.
Then I could mention Pascal's triangle and point out that Pascall is a manufacturer of candy here in Australia, but I won't do that because I think you said that you didn't really like puns ;-)
The second answer doesn't seem to simplify to a single choose function but perhaps it's a simple combination of choose functions?
Yes, that's correct, though I don't think a third person reading this will understand what you mean by "ghost" students.
ReplyDeleteSome questions about the second problem: Is there a nice way to solve it in the case where the two teams have to square off against each other man-to-man (in other words, you're assigning a selected person from class B to each selected person from class A)? By "nice" I mean a formula that doesn't involve long complicated products or sums, just a simple closed form. (A plain English way to put this question is "how many ways can you assign 7 bowling balls to 7 people if you don't know how many people are going to be bowling?")
ReplyDeleteFurthermore, is there a nice generalization of the original solution for the case in which the class sizes aren't equal?
I don't know, I'd have to think about it.
ReplyDeleteFor the first question (about bowling balls), I doubt that there is any closed form expression. But you can generalize the second problem to classes of unequal size.
ReplyDelete