MathDB

Find the number of M-partitions of A

Source: China Team Selection Test 2003, Day 2, Problem 2

October 13, 2005

combinatorics unsolvedcombinatorics

Problem Statement

Suppose

A=\{1,2,\dots,2002\}

and

M=\{1001,2003,3005\}

.

B

is an non-empty subset of

A

.

B

is called a

M

-free set if the sum of any two numbers in

B

does not belong to

M

. If

A=A_1\cup A_2

,

A_1\cap A_2=\emptyset

and

A_1,A_2

are

M

-free sets, we call the ordered pair

(A_1,A_2)

a

M

-partition of

A

. Find the number of

M

-partitions of

A

.

Back to Problems View on AoPS