MathDB

Let

k

and

n

be positive integers such that

k\le n-1

. Let

S:=\{1,2,\ldots,n\}

and let

A_1,A_2,\ldots,A_k

be nonempty subsets of

S

. Prove that it is possible to color some elements of

S

using two colors, red and blue, such that the following conditions are satisfied:
(i) Each element of

S

is either left uncolored or is colored red or blue. (ii) At least one element of

S

is colored. (iii) Each set

A_i~(i=1,2,\ldots,k)

is either completely uncolored or it contains at least one red and at least one blue element.

Problem 3