Complementary Counting

Complementary Counting consists in counting the total number of elements (universal set) and subtracting the number of elements that do not satisfy the given property (complementary set).

Problem (Puerto Rico, 2011)

How many six-digit numbers have at least one even digit?

Solution

Answer: $9 \cdot 10^5-5^6$.

Let $A$ be all six-digit numbers that have at least one even digit. Let us first find number of elements in the universal set $U$, i.e. the total number of six-digit numbers:

$$ |U| = 9 \cdot 10 \cdot 10 \cdot 10 \cdot 10 \cdot 10 = 9 \cdot 10^5$$

 

Now let us find the number of elements in the complementary set $A^{c}$, i.e. the number of six-digit numbers that do not have even digits. This means that all the digits should be odd and

$$|A^c| = 5 \cdot 5 \cdot 5 \cdot 5 \cdot 5 \cdot 5 = 5^6$$

Therefore the number of elements in the set $A$ is equal to

$$|A| = |U| – |A^c| = 9 \cdot 10^5-5^6$$

---