Monday, December 6, 2010

Candy combinatorics

Back in the day I used to solve puzzles like these for a hobby.  It occurs to me that one of the things I really liked about it is that I got to "discover" different kinds of math.  Maybe I should make more math puzzles?

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 same number can also be written as "twenty choose three" or C(20,3).

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