0
$\begingroup$

I've reviewed this question and a little stuck on the formula presented: Integers divisible by 4 but not by 3 and 16 and was hoping someone could provide some additional details as to the logic being applied. I've tried to write it out as follows:

Let $A = 3|n$ , $B = 4|n $ and $C = 3 \bullet 4 | n$ where $|C| = |A \cap B| = \lfloor\frac{|A|}{4}\rfloor = \lfloor\frac{|B|}{3}\rfloor$

I understood the formula as follows: $|A\cup \overline B| = |A| - |A \cap B| $ but can I transform this into the format: $|A\cup \overline B| = |A| + |\overline B| - |A \cap \overline B| $ or vice versa?

I tried the following to show show that $|A \cup B| = |A| + |B| - |A \cap B| = |A \cap \overline B| - |\overline B|$ $= |\overline{\overline{A \cap \overline B}}| - |\overline B|$ $= |\overline{\overline A \cup B| } - |\overline B|$

$|U| - |\overline A \cup B| - |\overline B| = |U| - |\overline A| - |B| - |\overline A \cap B| - |\overline B|$ ... which I can't seem to finish.

$\endgroup$
2
  • $\begingroup$ Inclusion exclusion $\endgroup$
    – Wuestenfux
    Mar 16 '19 at 16:25
  • $\begingroup$ I think i over thought this one... $A \cup \overline B = A - B = |A| - |A \cap B| $ $\endgroup$ Mar 16 '19 at 17:09
1
$\begingroup$

You've got some issues with your approach. Let me address them point by point.

Let $A = 3|n$ , $B = 4|n $ and $C = 3 \bullet 4 | n$ where $|C| = |A \cup B| = \lfloor\frac{|A|}{4}\rfloor = \lfloor\frac{|B|}{3}\rfloor$

One issue here is a bit of a nitpick: you seem to want $A,B,C$ to be statements and sets at the same time. Rather, I think you mean $A=\{n\in U:3\mid n\},B=\{n\in U:4\mid n\},C=\{n\in U:12\mid n\},$ where $U=\{n\in\Bbb Z^+:100\le n\le 999\}.$ Another issue may simply be a typo: we should have $C=A\cap B,$ not $C=A\cup B.$

I understood the formula as follows: $\left|A\cup \overline B\right| = |A| - |A \cup B| $ but can I transform this into the format: $|A\cup \overline B| = |A| + |\overline B| - |A \cap \overline B| $ or vice versa?

Here again, I suspect a typo: we should have $\left|A\cap \overline B\right| = |A| - |A \cap B|,$ assuming that $\overline B$ refers to the relative complement of $B$ in $U.$ Your second formula here is correct, but we aren't interested in the numbers that are divisible by $3$ or not divisible by $4,$ so it isn't relevant.

I tried the following to show show that $$\begin{eqnarray}|A \cup B| &=& |A| + |B| - |A \cap B|\\ &=& \left|A \cap \overline B\right| - \left|\overline B\right|\\ &=& \left|\overline{\overline{A \cap \overline B}}\right| - \left|\overline B\right|\\ &=& \left|\overline{\overline A \cup B}\right| - \left|\overline B\right|\\ &=& |U| - \left|\overline A \cup B\right| - \left|\overline B\right|\\ &=& |U| - \left|\overline A\right| - |B| - \left|\overline A \cap B\right| - \left|\overline B\right|...\end{eqnarray}$$ which I can't seem to finish.

This again doesn't seem to be relevant, but I'll talk about it, anyway. It is true that $|A \cup B| = |A| + |B| - |A \cap B|,$ since we're dealing with finite sets. By the formula $|A\cap \overline B| = |A| - |A \cap B|,$ we should then conclude that $$|A\cup B| = |A\cap \overline B|+|B|,$$ instead.

You've correctly applied DeMorgan's laws to $A\cap\overline B$, so that $$\left|\overline{\overline A \cup B}\right| - \left|\overline B\right| = |U| - \left|\overline A \cup B\right| - \left|\overline B\right|,$$ but then went off the rails again. Since $\left|\overline A \cup B\right|=\left|\overline A\right|+|B|-\left|\overline A\cap B\right|,$ we should instead find that $$|U| - \left|\overline A \cup B\right| - \left|\overline B\right|=|U|-\left|\overline A\right|-|B|+\left|\overline A\cap B\right|-\left|\overline B\right|.$$


Now, instead, we'll use the formula $$|A\cap \overline B| = |A| - |A \cap B|,$$ or more simply, $$|A\cap \overline B| = |A| - |C|.\tag{1}$$ All that's left is to calculate $|A|$ and $|C|.$ I'll take care of $A,$ and I'll leave $C$ to you.

Just to spoil it, I'll let you know that $$|A|=\frac{|U|}3=\frac{900}3=300.$$ But why is that? Note that in each of the sets $$\{100,101,102\},\{103,104,105\},\{106,107,108\},$$ there is exactly one element that is divisible by $3,$ and these sets have no elements in common More generally, for any integer $n,$ the set $\{99+3n-2,99+3n-1,99+3n\}$ has exactly one element divisible by $3,$ and if $m$ is an integer with $m\ne n,$ then $$\{99+3n-2,99+3n-1,99+3n\}\cap\{99+3m-2,99+3m-1,99+3m\}=\emptyset.$$ Now, note that $$U=\bigcup_{n=1}^{300}\{99+3n-2,99+3n-1,99+3n\},$$ so the number of elements in $A$ is the same as the number of $3$-element sets we've partitioned $U$ into, which is $\frac{900}3=300.$

$\endgroup$
1
  • $\begingroup$ Thank you for the detailed explanation. I corrected the typo. $\endgroup$ Mar 16 '19 at 17:21

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.