0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – orlp Jul 26 at 14:49
  • $\begingroup$ @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 $\endgroup$ – Gray_Rhino Jul 26 at 15:07
  • 1
    $\begingroup$ 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? $\endgroup$ – plop Jul 26 at 16:05
  • $\begingroup$ @plop I have to find all 5 subsets satisfying the above condition. $\endgroup$ – Gray_Rhino Jul 27 at 1:07
2
$\begingroup$

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:

enter image description here

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @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). $\endgroup$ – Gray_Rhino Jul 27 at 1:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Dmitry Jul 27 at 1:44
  • $\begingroup$ 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 $\endgroup$ – Gray_Rhino Jul 27 at 1:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.