2006 Canadian MO Problems/Problem 1

Problem

Let $f(n,k)$ be the number of ways distributing $k$ candies to $n$ children so that each child receives at most two candies. For example, $f(3,7)=0$ , $f(3,6)=1$ , and $f(3,4)=6$ . Evaluate $f(2006,1)+f(2006,4)+f(2006,7)+\dots+f(2006,1003)$ .

Solution

$x_1 + \cdots + x_{2006} = k$

$x_i \in \{0,1,2\}$

$\therefore$ generating function for one student is $f(x) = (x^0 + x^1 + x^2)$

generating function for $n$ many students is $f(x)^n = (x^0 + x^1 + x^2)^n$

$\therefore$ generating function for 2006 many students is $(x^0 + x^1 + x^2)^{2006}$

Let $g(x) = (x^0 + x^1 + x^2)^{2006} = (1 + x + x^2)^{2006}$

$g(x) = \sum_{k=0}^{2 \cdot 2006} f(2006, k) x^k$

$\sum_{k=0}^{2 \cdot 2006} f(2006, k) x^k = g(x)$

$\therefore$ coefficient of $x^{3k+1}$ is $f(2006, 3k+1)$ , \quad $k \in \{0,1,\dots\}$

Take $h(x) = g(x) x^{-1} = \frac{(1 + x + x^2)^{2006}}{x}$

Then $\sum_{k=1}^{1337} f(2006, 3k+1)$ is the sum of the coefficients of $x^{3m},\ m \in \mathbb{N}$ in $h(x)$

$\omega = e^{2\pi i/3}$ \quad (third root of unity)

and since $1 + \omega + \omega^2 = 0$

the other coefficients vanish when we add up

$g(\omega^2) + g(\omega) + g(1) = \frac{(1 + \omega + \omega^2)^{2006}}{\omega} + \frac{(1 + \omega^2 + \omega^4)^{2006}}{\omega^2} + \frac{3^{2006}}{1}$

$= \frac{3^{2006}}{1} + \frac{0}{\omega^2} + \frac{0}{\omega} = 3^{2006}$

and since we added up the same coefficient thrice, we need to divide it by $3$

$\therefore \sum_{k=1}^{1337} f(2006, 3k+1) = \frac{3^{2006}}{3} = 3^{2005}$ ~Ishan

2006 Canadian MO (Problems)
Preceded by First question	1 • 2 • 3 • 4 • 5	Followed by Problem 2

Page

Toolbox

Search

2006 Canadian MO Problems/Problem 1

Problem

Solution

See also