Task using principle of inclusions and exclusions.

Question

Let $A = \{ 1,.....,100000\}$. Using principle of inclusions and exclusions determine cardinality $B$. Let $B$ be such subset $A$ that $e \in B \iff e $ is a number which contains at least one digit from $\{ 3,6,9\}$ I have a problem with counting such numbers.

Answer 1

An easy way to solve this is to find out how many numbers do not contain at least one digit from $\{3,6,9\}$, then to subtract that from $100000$. However, that does not use the Inclusion–exclusion principle. Unless, of course, the formula $|X^c|=|U|-|X|$ is considered part of that principle.

Here is a way that does use the principle. $$|X \cup Y \cup Z|=|X|+|Y|+|Z|-|X \cap Y| - |X \cap Z| - |Y \cap Z| + |X \cap Y \cap Z|$$

First, it is easier to consider the set from $0$ to $99999$ rather than from $1$ to $100000$: we will get the same answer, and this way we are working with all five-digit numbers (some of them with leading zeros).

We let X be the subset of A "contains at least one $3$" and similarly for B and C. You are then looking for cardinality of $B=X \cup Y \cup Z$. Due to symmetry, many sizes are equal, and we get $$|B|=3 \cdot |X|-3 \cdot |X \cap Y|+|X \cap Y \cap Z|$$

To find $|X|$, consider how many numbers in $A$ have the first digit $3$, then multiply that by the number of ways to choose one digit out of five (i.e. the permutations of $1$ out of $5$).

To find $|X \cap Y|$, consider how many numbers in $A$ have the first two digits $36$ (in that order), then multiply that by the number of ways to choose two digits out of five (remembering that order does count: i.e. the permutations of $2$ out of $5$).

To find $|X \cap Y \cap Z|$, consider how many numbers in $A$ have the first three digits $369$ (in that order), then multiply that by the number of ways to choose three digits out of five (remembering that order does count: i.e. the permutations of $3$ out of $5$).

Then use the formula for $|B|$ above.

I told you the other way was easier! I can think of yet another way that combines the inclusion-exclusion principle with the first method I mentioned. That way avoids counting the permutations and the multiplications. Let me know if you want that.