Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2006 Canadian MO Problems/Problem 1"
 
(12 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
 
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}}
 
  
 +
==Solution==
 +
<math>x_1 + \cdots + x_{2006} = k</math>
 +
 +
<math>x_i \in \{0,1,2\}</math>
 +
 +
<math>\therefore</math> generating function for one student is <math>f(x) = (x^0 + x^1 + x^2)</math>
 +
 +
generating function for <math>n</math> many students is <math>f(x)^n = (x^0 + x^1 + x^2)^n</math>
 +
 +
<math>\therefore</math> generating function for 2006 many students is <math>(x^0 + x^1 + x^2)^{2006}</math>
 +
 +
Let <math>g(x) = (x^0 + x^1 + x^2)^{2006} = (1 + x + x^2)^{2006}</math>
 +
 +
<math>g(x) = \sum_{k=0}^{2 \cdot 2006} f(2006, k) x^k</math>
 +
 +
<math>\sum_{k=0}^{2 \cdot 2006} f(2006, k) x^k = g(x)</math>
 +
 +
<math>\therefore</math> coefficient of <math>x^{3k+1}</math> is <math>f(2006, 3k+1)</math>, \quad <math>k \in \{0,1,\dots\}</math>
 +
 +
Take <math>h(x) = g(x) x^{-1} = \frac{(1 + x + x^2)^{2006}}{x}</math>
 +
 +
Then <math>\sum_{k=1}^{1337} f(2006, 3k+1)</math> is the sum of the coefficients of <math>x^{3m},\ m \in \mathbb{N}</math> in <math>h(x)</math>
 +
 +
<math>\omega = e^{2\pi i/3}</math> \quad (third root of unity)
 +
 +
and since <math>1 + \omega + \omega^2 = 0</math>
 +
 +
the other coefficients vanish when we add up
 +
 +
<math>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}</math>
 +
 +
<math>= \frac{3^{2006}}{1} + \frac{0}{\omega^2} + \frac{0}{\omega} = 3^{2006}</math>
 +
 +
and since we added up the same coefficient thrice, we need to divide it by <math>3</math>
 +
 +
<math>\therefore \sum_{k=1}^{1337} f(2006, 3k+1) = \frac{3^{2006}}{3} = 3^{2005}</math>
 +
~Ishan
 
==See also==
 
==See also==
 
*[[2006 Canadian MO]]
 
*[[2006 Canadian MO]]
  
 
{{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
 
−
 
−
:
 

Latest revision as of 12:22, 20 May 2025

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

See also

2006 Canadian MO (Problems)
Preceded by
First question 		1 • 2 • 3 • 4 • 5 Followed by
Problem 2
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_Canadian_MO_Problems/Problem_1&oldid=248829"