Answer to January 18, 1999 Problem

Candy Problem
from Problem Solving A Handbook for Teachers
by Krulik and Rudnik

In how many ways can three people divide 25 pieces of candy so that each person gets at least one piece?
Not all of the pieces must be distributed. For example, one way that the candy can be distributed is each person getting one piece.


Solution:

There are 2,300 ways to distribute the pieces of candy! (there are 276 different ways to distribute ALL 25 pieces).

You can distribute 3 pieces of candy in only one way.
You can distribute 4 pieces of candy in 3 ways: 1-1-2; 1-2-1; 2-1-1
You can distribute 5 pieces of candy in 6 ways: 1-1-3; 1-3-1; 3-1-1; 2-2-1; 2-1-2; 1-2-2

Prepare a table to help analyze the results:
Number of
pieces of candy		 Number of
ways to distribute
3 1
4 3
5 6
6 10
7 15
... ...
n (n-1)(n-2) / 2
So, for 25 pieces of candy,
(24)(23) / 2 = 12 x 23 = 276

Then the sum of these triangular numbers
1 + 3 + 6 + 10 + ... + 276 = 2,300

Correctly solved by:

1. Michael Leatherman Norfolk, VA