2
$\begingroup$

Given that $$ |A| = 5 \\ |B| = 6 \\ |C| = 7 \\ |\Omega| = 10 \\ A \subseteq (B \cup C) $$

Determine the min and max numbers of elements from $$(B \cup A) \bigtriangleup (C \cap A)$$

I tried to solve this by first simplifying the above statement doing $$[(B \cup A) \cap (C \cap A)^{c}] \cup [(B \cup A)^{c} \cap (C \cap A)] \\ [(B \cup A) \cap (C \cap A)^{c}] \cup [(B^{c} \cap A^{c}) \cap (C \cap A)] \\ [(B \cup A) \cap (C \cap A)^{c}] \cup \emptyset \\ (B \cup A) \cap (C \cap A)^{c} $$

Then i drew the venn diagrams that would represent the max and min case for $(B \cup A) \cap (C \cap A)^{c}$:

min case max case

And according to this:

  • the minimum number of elements is 1
  • the maximum number of elements is 4

Question: Would this be correct? If so, is there any other faster way that can let me solve the exercise without drawing venn diagrams and trying to configure the elements for both cases?

Thanks so much in advance.

$\endgroup$
  • $\begingroup$ In your right hand "max" case, the 6 is in $B \cup A$ and in $C \cap A$, so not in the symmetric difference. To me the right example only has the 1,2,3 in the symmetric difference. $\endgroup$ – coffeemath Jul 23 '13 at 8:50
  • $\begingroup$ Not sure if i'm getting it but wouldn't that be more than 5 elements for A if i put one more element or say $6$ in $C \cap A$ ? $\endgroup$ – zv.diego Jul 23 '13 at 8:56
  • 1
    $\begingroup$ You really ought to draw your Venn diagrams to show $A\subseteq B\cup C$. $\endgroup$ – Brian M. Scott Jul 23 '13 at 8:57
  • 1
    $\begingroup$ Is this $(B \cup A) \bigtriangleup (C \cap A)^{c}$ (as in the title) or $(B \cup A) \bigtriangleup (C \cap A)$ (i.e. no complement, as in the text)? $\endgroup$ – dtldarek Jul 23 '13 at 9:49
  • $\begingroup$ @dtldarek wow, how could i've missed that, so sorry i just fixed it, it should be the non complement as in the text, thanks! $\endgroup$ – zv.diego Jul 23 '13 at 10:27
3
$\begingroup$

Use the fact that $X\bigtriangleup Y=(X\cup Y)\setminus(X\cap Y)$, with $X=B\cup A$ and $Y=C\cap A$:

$$\begin{align*} (B\cup A)\cup(C\cap A)&=(B\cup A\cup C)\cap(B\cup A\cup A)&&\text{distributivity}\\ &=(B\cup C)\cap(B\cup A)&&A\subseteq B\cup C\\ &=B\cup(C\cap A)&&\text{distributivity} \end{align*}$$

and

$$\begin{align*} (B\cup A)\cap(C\cap A)&=(B\cap C\cap A)\cup(A\cap C\cap A)&&\text{distributivity}\\ &=(B\cap C\cap A)\cup(C\cap A)\\ &=C\cap A\;, \end{align*}$$

so

$$\begin{align*} (B \cup A) \bigtriangleup (C \cap A)&=\Big(B\cup(C\cap A)\Big)\setminus(C\cap A)\\ &=B\setminus(C\cap A)\;. \end{align*}$$

Corrected:

To make this large, you want to make $A\cap B\cap C$ as small as possible, and to make it small, you want to make $A\cap B\cap C$ as large as possible. If you put the $4$ elements of $\Omega\setminus B$ into both $A$ and $C$, you can arrange the rest so as to make $A\cap B\cap C=\varnothing$, and you certainly can’t make it any smaller! At the other extreme, if $A\subseteq B\cap C$, then $A\cap B\cap C=A$ and has cardinality $5$. Thus, the range of cardinalities for the symmetric difference is from $6-5=1$ to $6-0=6$.

$\endgroup$
  • $\begingroup$ thanks much, always there to help me out. I've got one question though, i just ran this on WA wolframalpha.com/input/… wolframalpha.com/input/… can you see that there is a difference between the two arrangements? $\endgroup$ – zv.diego Jul 23 '13 at 10:23
  • 1
    $\begingroup$ @Diego: You’re welcome. Note that the W|A diagram doesn’t include the information that $A\subseteq B\cup C$; if you add that information, the pink region containing the letter $a$ disappears, and you just have the three pink regions inside the $b$ circle, which do indeed represent $B\setminus(A\cap C)$. $\endgroup$ – Brian M. Scott Jul 23 '13 at 10:32
  • $\begingroup$ @BrianMScott I'm still struggling here with the max case, i can't see how there is 1 element in $A \cap B \cap C$ if i can arrange it in this way where $B \setminus (C \cap A)$ would have a max of 6 elements. $\endgroup$ – zv.diego Jul 23 '13 at 21:09
  • 1
    $\begingroup$ @Diego: You’re quite right: that was a mental hiccup on my part. I should have checked with pencil and paper. I’ve corrected it now. $\endgroup$ – Brian M. Scott Jul 23 '13 at 21:26
  • $\begingroup$ @BrianMScott Nice!, kept thinking about it for a long while haha, thanks again :) $\endgroup$ – zv.diego Jul 23 '13 at 21:33
1
$\begingroup$

A more systematic approach would be to partition $\Omega$ into $S_0, \ldots S_7$ as all possible combinations of $A$, $B$ and $C$, and translate \begin{align} A &= S_1 \uplus S_3 \uplus S_5 \uplus S_7, \\ B &= S_2 \uplus S_3 \uplus S_6 \uplus S_7, \\ C &= S_4 \uplus S_5 \uplus S_6 \uplus S_7, \\ (B \cup A) \bigtriangleup (C \cap A) &= (S_{1\uplus 2 \uplus 3 \uplus 5 \uplus 6 \uplus 7}) \bigtriangleup (S_{5 \uplus 7}) \\ &= S_1 \uplus S_2 \uplus S_3 \uplus S_6. \end{align}

From $A \subseteq B \cup C$ we know that $S_1 = \varnothing$ and that gives us the following:

\begin{align} s_1 &= 0\\ s_1+s_3+s_5+s_7 &= 5 \\ s_2+s_3+s_6+s_7 &= 6 \\ s_4+s_5+s_6+s_7 &= 7 \\ s_0+s_1+s_2+s_3+s_4+s_5+s_6+s_7 &= 10 \end{align}

where $s_i = |S_i|$ (don't forget about the $0 \leq s_i$ constraints). Now your question can be stated as: what is the maximum and minimum of $s_1+s_2+s_3+s_6$? Note that $s_1 = 0$ and $S_2 \uplus S_3 \uplus S_6$ is exactly $B \setminus (C \cap A)$ (as in Brian's answer).

I hope this helps ;-)

Edit: Cleared issue with $(B \cup A) \triangle (C\cap A)$ versus $(B \cup A) \triangle (C \cap A)^c$.

$\endgroup$
  • $\begingroup$ It seems the OP wants to bound element count of $(B \cup A) \Delta (C \cap A)$, without the extra complement symbol. The question's title had that complement symbol in it, but in the body of the question it was not there. $\endgroup$ – coffeemath Jul 23 '13 at 9:49
  • $\begingroup$ @coffeemath Yeah, I've just realized that and asked the OP for clarification. Anyway, thanks for noticing ;-) $\endgroup$ – dtldarek Jul 23 '13 at 9:51
  • $\begingroup$ @dtldarek I seem not to be familiar to this notation, do you mind if i ask you for any lecture link or a few keywords so i can look it up on google? thanks! $\endgroup$ – zv.diego Jul 23 '13 at 10:47
  • 1
    $\begingroup$ @DiegoZacarias $A \uplus B$ is just the disjoint sum, while I wrote $S_{x \uplus y}$ to denote $S_x \uplus S_y$ because it would otherwise make the post less readable. $\endgroup$ – dtldarek Jul 23 '13 at 10:53

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.