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)$ . apparently the proposers didnt get a closed form answer of this problem and somehow the previous solution here was wrong, this is standard roots of unity filter Let $f(n, k)$ be the number of solutions $(x_1, x_2, \ldots, x_n)$ to the equation $x_1 + x_2 + \cdots + x_n = k$ where $x_i \in \{0, 1, 2\}$ for $1 \le i \le n$ . Equivalently, $f(n, k)$ is the coefficient of $x^k$ in the generating function $A(x) = (1 + x + x^2)^n.$ Define $A(x) = \sum_{k=0}^{\infty} f(n, k) x^k.$ Let $\omega \ne 1$ be a primitive third root of unity. Then $\frac{1}{3} \left[ A(x) + \omega^2 A(\omega x) + \omega A(\omega^2 x) \right] = f(n,1)x + f(n,4)x^4 + f(n,7)x^7 + \cdots.$ Plugging in $x = 1$ , we obtain $\frac{1}{3} \left[ A(1) + \omega^2 A(\omega) + \omega A(\omega^2) \right] = f(n,1) + f(n,4) + f(n,7) + \cdots.$ We compute: $A(1) = 3^n, \quad A(\omega) = 0, \quad A(\omega^2) = 0,$ so the desired sum is $\frac{1}{3} \cdot 3^n = 3^{n-1}.$ Thus, the final answer is $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

See also