Complementary counting

In combinatorics, complementary counting is a counting method where one counts what they don't want, then subtracts that from the total number of possibilities. In problems that involve complex or tedious casework, complementary counting is often a far simpler approach. A large hint that complementary counting may lead to a quick solution is the phrase "not" or "at least" within a problem statement.

More formally, if $B$ is a subset of $A$ , complementary counting exploits the property that $|B| = |A| - |B^c|$ , where $B^c$ is the complement of $B$ . In most instances, though, $A$ is obvious from context.

Examples

Here are some problems where complementary counting is particularly effective. Other solution methods exist for some of these problems, but they are more convoluted than a complementary approach.

Example 1

How many positive integers less than $100$ are not a multiple of five?

Solution: We use a complementary approach. The total number of positive integers, with no restrictions, is $99$ integers. What we don't want are the multiples of five; these are $5, 10,..., 95$ or $1 \cdot 5, 2 \cdot 5,..., 19 \cdot 5$ , so there are $19$ multiples of five. Thus, our answer is is $99-19 = 80$ . $\square$

Example 2

2006 AMC 10A Problem 21: How many four-digit positive integers have at least one digit that is a 2 or a 3?

Solution: We use a complementary approach. With no restrictions, there are $9000$ four-digit positive integers. What we don't want are the four-digit integers with no digit that is a two or three, Using a constructive approach, the first digit can be seven integers; $1, 4, 5, 6, 7, 8,$ and $9$ . It's worth noting that the first digit cannot be zero, or else it ceases to be four-digit. The second, third, and fourth digits can be zero, however; as a result, they have eight options. So, our total number of two-and-three-free numbers is $7 \cdot 8^3 = 3584$ . Hence, our final answer is $9000 - 3584 = 5416$ , as desired. $\square$

Example 3

Sally is drawing seven houses. She has four crayons, but she can only color any house a single color. In how many ways can she color the seven houses if at least one pair of consecutive houses have the same color?

Solution: Use complementary counting. First, we find the total colorings without restriction, which we do by constructing them. She has four options for what color the first house can be, four options for the second, and so on. Hence, there are $4^7 = 16384$ ways she can color the four houses.

Next, we find the possibilities where every house's next-door neighbor is a different color. Using a constructive approach, she has four options for the color of the first house. We have to make sure the next house is a different color; as a result, there are only three options for the color of the second house, with the color of the first house unavailable. By similar logic, there are 3 options for the third house, and so on for every other house. Combining these yields $4 \cdot 3^6 = 2916$ possibilities if every house must be a different color.

Putting these two together, there are $16384 - 2916 = 13486$ ways she can color the seven houses four colors if at least one pair of consecutive houses must be the same color. $\square$

Video

This is a video explaining the basics of casework, complementary counting, and overcounting (more specifically, the Principle of Inclusion-Exclusion): https://youtu.be/Zhsb5lv6jCI

Introductory

Intermediate

2004 AIME I Problems/Problem 15

Page

Toolbox

Search