2006 Canadian MO Problems/Problem 1
Problem
Let 
be the number of ways distributing 
candies to 
children so that each child receives at most two candies. For example, 
, 
, and 
. Evaluate 
.
Solution
This problem needs a solution. If you have a solution for it, please help us out by adding it.
See also
| 2006 Canadian MO (Problems) | ||
| Preceded by First question |
1 • 2 • 3 • 4 • 5 | Followed by Problem 2 |
The number of ways of distributing k candies to 2006 children is equal to the number of ways of distributing 0 to a particular child and k to the rest, plus the number of ways of distributing 1 to the particular child and k ¡ 1 to the rest, plus the number of ways of distributing 2 to the particular child and k ¡ 2 to the rest. Thus f(2006; k) = f(2005; k) + f(2005; k ¡ 1) + f(2005; k ¡ 2), so that the required sum is 1 + 1003 X k=1 f(2005; k) : In evaluating f(n; k), suppose that there are r children who receive 2 candies; these r children can be chosen in ¡n r ¢ ways. Then there are k ¡ 2r candies from which at most one is given to each of n ¡ r children. Hence f(n; k) = b X k=2c r=0 µ n r ¶µ n ¡ r k ¡ 2r ¶ = X1 r=0 µ n r ¶µ n ¡ r k ¡ 2r ¶
with ¡ x y ¢ = 0 when x < y and when y < 0. The answer is 1003 X k=0 X1 r=0 µ 2005 r ¶µ2005 ¡ r k ¡ 2r ¶ = X1 r=0 µ 2005 r ¶ 1003 X k=0 µ 2005 ¡ r k ¡ 2r ¶
