Combinations of set unions

Question

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.

Answer 1

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\}$