Let $M$ be the set of all integers from $1$ to $2013$. Each subset of $M$ is given one of $k$ available colors, with the only condition that if the union of two different subsets $A$ and $B$ is $M$, then $A$ and $B$ are given different colors. What is the least possible value of $k$?
Problem
Source:
Tags: induction, combinatorics proposed, combinatorics
anthony_ecu
23.08.2014 22:19
Let show to M with n elements, the least possible value of k is n+1 by induction. n=1 there are 2 subset and the union is M so we have to give them 2 colors. Suppose that n=k the least possible value is k+1 it's clear that if C is a subset when n=k => C is a subset when n=k+1, so we have 2 kind of subset, C that is a subset of n=k, is a subset of n=k+1,too and C+{k+1}=C' that is a subset just to n=k+1, so the color that we had given to C, now we will give to C', and now all the subset the same kind of C doesn't have the element k+1, so we can give them to all of them the same color diferent to the others, so we have used k+2 colors, and we have finished the induction, the answer to M=2013 is 2014.
junioragd
26.08.2014 15:13
There is a more simpler proof.Just consider sets {1,2,...2013} and all subsets having 2012 elements.We picked this 2014 subsets and it is clear that the union of every two from this 2014 subsets is M,so we need at least 2014 colors.For coloring,color them like this:consider all subsets of {2,3,...2013} and color them with 1.Then,consider all subsets of {1,3,4,...2013} that are not already chosen and go on with this process,so we are done.
RodSalgDomPort
18.12.2018 21:24
Well, a more natural coloration with 2014 colors: Let S_i be the set of the subsets of M - {i} for all i, 0<i<2014. For example, S_5 is the set of subsets from {1,2,3,4,6,7...,2013} which includes the empty set. Now, paint the elements from S_i with color i for all i, starting with i = 1 and following the crescent order of i until 2013. Literally, imagine yourself painting the sets. So, if a set is of the color k and you paint it with color j after had painting it with the color i, this subset will be of the color j. Easily, 2 subsets with the same color implies that there exist x such that they both belongs to S_x. So their union can't be M, since x will be missing. Realize that you've painted all the subsets but M. Now you paint M with color 2014. You've used 2014 colors. Now, you just need to take T_i for all i where T_i = M -{i} and take also M. These are 2014 sets which may not have the same color. So, the answer is 2014
parmenides51
16.09.2021 10:38
solved from here
mavropnevma wrote:
Solution 4. When $A\cap B = \emptyset$, $A\cup B = M$, it means $B= \overline{A}$. That means two colours are necessary, but also enough, since we can pair the subsets of $M$ in complementary pairs $(A, \overline{A})$, and arbitrarily assign one colour to one element of the pair and the other to the other element of the pair.
EDIT. This was written under the mistaken understanding that the condition was for disjoint, rather than distinct subsets $A$ and $B$ (an error in translation). Now that I made the correction, an appropriate solution follows.
Consider the set $M = \{1,2,\ldots,n\}$. At least $n+1$ colours are needed, since the union of any two of the $n+1$ subsets $M, M\setminus \{1\}, M\setminus \{2\},\ldots, M\setminus \{n\}$ is equal to $M$, so they all have to bear distinct colours.
But $n+1$ colours are also sufficient; colour $M$ with the colour $c_{n+1}$ (the only one bearing this colour), and colour any other subset $A$ with the colour $c_i$, where $1\leq i\leq n$ is the least number not contained in $A$. Therefore, if $A$ and $B$ bear a same colour $c_i$, $1\leq i \leq n$, then $i$ belongs to neither $A$, nor $B$, so $i\not \in A\cup B$, thus $A\cup B \neq M$.