# Positive Integers between 100 and 999 inclusive that are divisible by 3 but not by 4?

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.

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

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.$$

• Thank you for the detailed explanation. I corrected the typo. Mar 16 '19 at 17:21