MathDB

Coloring the subsets of a set

Source: Bulgarian NMO 2017, 3-rd round.

April 20, 2017

combinatoricsposet

Problem Statement

Let

M

be a set of

2017

positive integers. For any subset

A

of

M

we define

f(A) := \{x\in M\mid \text{ the number of the members of }A\,,\, x \text{ is multiple of, is odd }\}

. Find the minimal natural number

k

, satisfying the condition: for any

M

, we can color all the subsets of

M

with

k

colors, such that whenever

A\neq f(A)

,

A

and

f(A)

are colored with different colors.

Back to Problems View on AoPS