How many positive integers, not exceeding 100, are multiples of 2 or 3 but not 4?
Hello, I was wondering how to solve problems like these. My thoughts are to count the number that are multiples of 2 but not 4, multiples of 3 but not 4, and then multiples of 6 but not 4, then use Principle of Inclusion and Exclusion as follows:
$$\left\lfloor \frac{100}{2} \times \frac{1}{2} \right\rfloor + \left\lfloor \frac{100}{3} \times \frac{3}{4} \right\rfloor - \left\lfloor \frac{100}{6} \times \frac{1}{2} \right\rfloor = 42,$$
but I am unsure as to if this is a valid solution. Can anybody confirm/deny that I am using Principle of Inclusion and Exclusion properly? Thanks!
What you did is not quite correct, although it does give the correct result. This is because each floor function in inclusion-exclusion is for just one set of divisions only, not multiple ones combined as you did, although combining them still sometimes gives the same values anyway, as it does in your case. An example where it doesn't work is if $102$ were used instead, since there are $26$ multiples of $2$ but not $4$, but your technique gives $\left\lfloor \frac{102}{4} \right\rfloor = 25$. Instead, as shown in \eqref{eq1A} below, using inclusion-exclusion appropriately gives $\left\lfloor \frac{102}{2} \right\rfloor - \left\lfloor \frac{102}{4} \right\rfloor = 51 - 25 = 26$.
The procedure you seem to be following is to start with the number of multiples of $2$, but not $4$. Next, add the number of multiples of $3$, but not $12$. Finally, since you double counted these, subtract the number of multiples of $6$, but not $12$. The principle of inclusion and exclusion then gives
$$\begin{equation}\begin{aligned} & \left(\left\lfloor \frac{100}{2} \right\rfloor - \left\lfloor \frac{100}{4} \right\rfloor \right) + \left(\left\lfloor \frac{100}{3} \right\rfloor - \left\lfloor \frac{100}{12} \right\rfloor \right) - \left(\left\lfloor \frac{100}{6} \right\rfloor - \left\lfloor \frac{100}{12} \right\rfloor \right) \\ & = (50 - 25) + (33 - 8) - (16 - 8) \\ & = 25 + 25 - 8 \\ & = 42 \end{aligned}\end{equation}\tag{1}\label{eq1A}$$
FYI, here's a bit simpler way to solve the problem. As you did, start with those numbers which are multiples of $2$ but not $4$, i.e., $2x$ with $x \in \{1, 3, \ldots, 49\}$, of which there are $25$ integers. Next, since it's a disjoint subset, you can just add the number of odd multiples of $3$, i.e., $3x$ with $x \in \{1, 3, \ldots, 33\}$, so there's $17$ of them. This then gives the same result as yours, i.e.,
$$25 + 17 = 42 \tag{2}\label{eq2A}$$
Note you can also get the same thing using inclusion-exclusion. This is done by, after dealing with the multiples of $2$ but not $4$, then adding the number of multiples of $3$ but not $6$, giving
$$\begin{equation}\begin{aligned} & \left(\left\lfloor \frac{100}{2} \right\rfloor - \left\lfloor \frac{100}{4} \right\rfloor \right) + \left(\left\lfloor \frac{100}{3} \right\rfloor - \left\lfloor \frac{100}{6} \right\rfloor \right) \\ & = (50 - 25) + (33 - 16) \\ & = 25 + 17 \\ & = 42 \end{aligned}\end{equation}\tag{3}\label{eq3A}$$
Also note that \eqref{eq1A} is basically the same as \eqref{eq3A} since the two $\left\lfloor \frac{100}{12} \right\rfloor = 8$ terms cancel each other out.