When is it possible to split three sets?

135 Views Asked by At

There are three sets, each of which contains some $2 k$ elements. The sets may overlap.

Is it possible to color the elements red and green, such that each set contains exactly $k$ red and $k$ green elements?

If $k$ is odd, then this may be impossible. For example, suppose the sets are: $$ S_1 = \{1,2,~~ 4,5,~~ 7,8,~~ \ldots, 3k-2, 3k-1 \} \\ S_2 = \{2,3,~~ 5,6,~~ 8,9,~~ \ldots, 3k-1, 3k \} \\ S_3 = \{3,1,~~ 6,4,~~ 9,7,~~ \ldots, 3k, 3k-2 \} $$ Each set contains exactly $2k$ elements. Each element appears in exactly two sets, so if there were exactly $k$ red elements in each set, the number of red elements overall should have been $3 k /2$ by double-counting. But this is impossible since $k$ is odd.

The remaining case is that $k$ is even. Is it always possible to split the sets in this case?