# Combinations of set unions

I have a set $$S = \{0,1,2,3,4,5,6,7,8,9\}$$. $$S_i \subset S$$ for $$i = {1,2,3,4,5}$$. Any three $$S_i$$ has the same union, that is $$S_1 \cup S_2\cup S_3 = S_1\cup S_2\cup S_4 = ...=S_3\cup S_4\cup S_5 = A$$ and no $$S_i\cup S_j = A$$. What is lexicoraphical least of such $$S_i$$s?
I have to write a Python code for this and I would appreciate any help that could direct me to find a solution. What should I know to be able to solve this problem in the shortest possible period? Also, if there's a better way to formulate this problem please do leave me comments with your suggestions. If the information is not sufficient I can clarify further.

• How do you define the 'lexicoraphical least of such $S_i$s' when there are multiple? Do you just wish to find a solution set of which any of them is minimized? Or should the greatest of the bunch be minimal? Or? – orlp Jul 26 '20 at 14:49
• @orlp A solution set of which any of them is minimized. For example, there would be 210 possible subsets of length 6. Let's suppose I order them and I need the first 5 that satisfy the above condition. [0,1,2] < [0,1,3] -> this is what I mean by lexicographical – Gray_Rhino Jul 26 '20 at 15:07
• You have defined, in the comment, an order for subsets. Lexicographic order. Which order do you want for sets of subsets? Also lexicographic? To exemplify what I am asking and make my example simpler I will assume that we need $2$ instead of $5$ subsets. If $S_1<S_2<S_3<S_4$ lexicographically, and $S_1,S_4$ is a solution and $S_2,S_3$ is also a solution, which one is the solution wanted? – plop Jul 26 '20 at 16:05
• @plop I have to find all 5 subsets satisfying the above condition. – Gray_Rhino Jul 27 '20 at 1:07
• – D.W. Jul 27 '20 at 2:59

I understood the problem as that we can select any $$S_i$$ satisfying these conditions. Then the answer is $$\{0, 1, 2, 3, 4, 5\}$$. The construction is unique in a certain sense.

Wlog we can assume that $$S=A$$ (otherwise, just remove redundant elements from $$S$$). I'll use $$A, B, C, D, E$$ instead of $$S_i$$. One way to arrive at a solution is to draw a Venn diagram for $$A, B, C$$ and to think about it:

What can we say about it:

• $$A \setminus (B \cup C) \ne \emptyset$$. Otherwise $$B \cup C = A \cup B \cup C = S$$. Similarly for $$B$$ and $$C$$.

• For $$D$$ we must have $$A \setminus (B \cup C) \subseteq D$$. Otherwise, $$B \cup C \cup D \ne B \cup C \cup A = S$$. Similarly for $$B$$ and $$C$$.

• For $$D$$ we must have $$A \cap C \setminus B \not \subseteq D$$. Otherwise (just look at the diagram), $$B \cup D = B \cup (A \setminus (B \cup C)) \cup (C \setminus (A \cup B)) \cup (A \cap C \setminus B) = S$$

• What we said for $$D$$ also holds for $$E$$. I.e. it must contain the symmetric difference but must not contain $$A \cap C \setminus B$$ and similar.

• We must have $$D \cup E \cup X = S$$ for $$X = A,B,C$$. Therefore, $$D \cup E \cup (A \cap B \cap C) = S$$. In particular, it means that $$A \cap B \cap C \not \subseteq D \cup E$$, since otherwise $$D \cup E = S$$.

Also, $$S \setminus (A \cap B \cap C) \subseteq D \cup E$$. Therefore, forgetting about symmetric difference: $$((A \cap C) \cup (A \cap B) \cup (B \cup C)) \setminus (A \cap B \cap C) \subseteq D \cup E$$ Therefore, while $$A \cap C \setminus B$$ doesn't belong to either $$D$$ or $$E$$, it belongs to their union.

Note that conditions above are necessary and sufficient. Putting this together:

• $$A \setminus (B \cup C)$$ must have at least one element, which also belongs to both $$D$$ and $$E$$. The same for $$B, C$$.
• $$A \cap C \setminus B$$ must have at least two elements: one belongs to $$D$$, another belongs to $$E$$. The same for other pairwise intersections.
• $$A \cap B \cap C$$ has at least one element, which doesn't belong to either $$D$$ and $$E$$.

Note that we've used all $$10$$ elements from $$S$$. All sets $$A,..,E$$ have $$6$$ elements, so we just select one of them to be $$S_1$$, and arrange elements in the sets so that $$S_1 = \{0,..,5\}$$

• @Dimitry Thank you very much for the answer. Your answer is correct for $S_1$. Any suggestions on how I can generate the other 4 subsets? I will try to understand your logic and generalize it for (n,m) instead of (5,3). – Gray_Rhino Jul 27 '20 at 1:33
• I don't think it'll be easy to generalize. It depends on the number of sets. Even for $(4,3)$ the construction is very different: you need $D$ to contain only symmetric differences, and therefore you can find an answer with $3$ elements. I mean, this question was definitely specifically forged with exactly these parameters. – user114966 Jul 27 '20 at 1:44
• The constraints are $1\leq n\leq 9$ and $0\leq m\leq 9$. If I can find some invariance the code will take care of different combinations. Your answer is directing me to the right path. Thanks again – Gray_Rhino Jul 27 '20 at 1:55