Difference between revisions of "2006 Canadian MO Problems/Problem 1"
m (→Solution: box) |
|||
| Line 8: | Line 8: | ||
{{CanadaMO box|year=2006|before=First question|num-a=2}} | {{CanadaMO box|year=2006|before=First question|num-a=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 | ||
| + | ¶ | ||
| + | : | ||
Revision as of 19:18, 25 September 2013
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 ¶
