Difference between revisions of "2006 Canadian MO Problems/Problem 1"

Revision as of 10:32, 30 November 2023

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

This problem needs a solution. If you have a solution for it, please help us out by adding it.

@@ Line 8: / Line 8: @@
 {{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
-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
-+
-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
-X
-k=0
-X1
-r=0
-µ
-r
-¶µ2005 ¡ r
-k ¡ 2r
-¶
-=
-X1
-r=0
-µ
-r
-¶ 1003 X
-k=0
-µ
-¡ r
-k ¡ 2r
-¶
-:

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

Page

Toolbox

Search

Difference between revisions of "2006 Canadian MO Problems/Problem 1"

Revision as of 10:32, 30 November 2023

Problem

Solution

See also