Difference between revisions of "2006 Canadian MO Problems/Problem 1"
(→Solution) |
|||
| (8 intermediate revisions by 2 users not shown) | |||
| Line 2: | Line 2: | ||
Let <math>f(n,k)</math> be the number of ways distributing <math>k</math> candies to <math>n</math> children so that each child receives at most two candies. For example, <math>f(3,7)=0</math>, <math>f(3,6)=1</math>, and <math>f(3,4)=6</math>. Evaluate <math>f(2006,1)+f(2006,4)+f(2006,7)+\dots+f(2006,1003)</math>. | Let <math>f(n,k)</math> be the number of ways distributing <math>k</math> candies to <math>n</math> children so that each child receives at most two candies. For example, <math>f(3,7)=0</math>, <math>f(3,6)=1</math>, and <math>f(3,4)=6</math>. Evaluate <math>f(2006,1)+f(2006,4)+f(2006,7)+\dots+f(2006,1003)</math>. | ||
==Solution== | ==Solution== | ||
| − | {{ | + | |
| + | <math>f(n, k) = \text{the number of ways to distribute } k \text{ candies among } n \text{ children such that each child gets at most 2 candies.} </math> | ||
| + | |||
| + | <math> \text{This corresponds to finding non-negative integer solutions to } x_1 + x_2 + \cdots + x_n = k \text{ where } 0 \leq x_i \leq 2 \text{ for all } i.</math> | ||
| + | |||
| + | <math>\text{ The generating function for one child is } 1 + x + x^2, \text{ and for } n \text{ children, it becomes } (1 + x + x^2)^n. </math> | ||
| + | |||
| + | <math>\text{ Rewriting, } 1 + x + x^2 = \frac{1 - x^3}{1 - x}, \text{ so } (1 + x + x^2)^n = \left(\frac{1 - x^3}{1 - x}\right)^n = (1 - x^3)^n (1 - x)^{-n}. </math> | ||
| + | |||
| + | <math> \text{ Using the binomial theorem, we expand } (1 - x^3)^n = \sum_{j=0}^n \binom{n}{j} (-1)^j x^{3j} \text{ and } (1 - x)^{-n} = \sum_{m=0}^\infty \binom{n + m - 1}{m} x^m. </math> | ||
| + | |||
| + | <math>\text{ The coefficient of } x^k \text{ in } (1 + x + x^2)^n \text{ is given by } f(n, k) = \sum_{j=0}^{\lfloor k/3 \rfloor} \binom{n}{j} (-1)^j \binom{n + k - 3j - 1}{k - 3j}. </math> | ||
| + | |||
| + | <math> \text{ For the problem, we sum } f(2006, k) \text{ over odd } k \text{ from } 1 \text{ to } 1003. </math> | ||
| + | |||
| + | <math>\text{ By symmetry of the generating function, } \sum_{k \text{ odd}} f(n, k) = 2^{n-1}. </math> | ||
| + | |||
| + | <math>\text{ Thus, for } n = 2006, \text{ the sum becomes } \sum_{k \text{ odd}} f(2006, k) = 2^{2006 - 1} = 2^{2005}. </math> | ||
| + | |||
| + | <math>\text{ Therefore, the final answer is } \boxed{2^{2005}}. </math> | ||
| + | |||
| + | ~sitar | ||
==See also== | ==See also== | ||
| Line 8: | Line 29: | ||
{{CanadaMO box|year=2006|before=First question|num-a=2}} | {{CanadaMO box|year=2006|before=First question|num-a=2}} | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
be the number of ways distributing 
candies to 
children so that each child receives at most two candies. For example, 
, 
, and 
. Evaluate 
.
