OBM 2003 Problem 2

Seja S um conjunto de n elementos. Determine o menor inteiro positivo k com a seguinte propriedade: dados quaisquer k subconjuntos distintos $A_1, A_2, \ldots, A_k$ de S, existe uma escolha adequada dos sinais + e – de modo que $S = A_1^{\pm} \cup A_2^{\pm} \cup \ldots \cup A_k^{\pm}$, onde $A_i^{+} = A_i$ e $A_i^{-} = S - A_i$ é o complementar de $A_i$ em relação a S.