Difference between revisions of "Complementary counting"

Revision as of 20:50, 25 May 2021

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 and is committed from mention.

Complementary probabilitiy

There is a probability equivalent of complementary counting. For any event, the probability it happens plus the probability it doesn't happen is one. Thus, we have the identity $P(A) = 1 - P(A^c).$ Like its counting analog, complementary probability often vastly simplifies tedious casework. Unlike complementary counting, though, it sees frequent use as an intermediate step, mainly because taking the complement is much easier in probability than in counting.

Examples

Here are some problems where complementary counting and probability are particularly effective. It's worth noting that complementary probability is not typically an intermediate step, but something upon which the framework of a solution is built upon.

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$

Example 4

2002 AIME I Problem 1 Many states use a sequence of three letters followed by a sequence of three digits as their standard license-plate pattern. Given that each three-letter three-digit arrangement is equally likely, the probability that such a license plate will contain at least one palindrome (a three-letter arrangement or a three-digit arrangement that reads the same left-to-right as it does right-to-left) is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m+n.$

Solution: We use complementary probability. So first, we find the probability that a license plate has no palindromes; in other words, the probability that the first and third numbers and letters are distinct. The probability the numbers are distinct is $\frac{9}{10}$ , and for the letters, it is $\frac{25}{26}$ . Multiplying these together gives that the probability that a license plate has no palindromes is $\frac{9}{10} \cdot \frac{25}{26} = \frac{225}{260} = \frac{45}{52}.$ Taking the complement of this, the probability a license plate has a palindrome is thus $1 - \frac{45}{52} = \frac{7}{52}$ . Hence, our answer is $7 + 52 = 59$ . $\square$

Example 5

2008 AMC 12B Problem 22: A parking lot has 16 spaces in a row. Twelve cars arrive, each of which requires one parking space, and their drivers chose spaces at random from among the available spaces. Auntie Em then arrives in her SUV, which requires 2 adjacent spaces. What is the probability that she is able to park?

Solution: Use complementary probability, where we find the probability that no two open spots are consecutive. With no restrictions, the total number of ways the 12 cars could park is $_{16} C_{12} = 1820$ , where $_n C_k$ is a combination. Finding how many permutations of the cars and spaces leave no two spaces next to each other is a more challenging task, though.

One might eventually think to treat this problem like a distribution, a stars-and-bars approach. Let the 12 cars be stars and the 4 spaces be bars. Here's one arrangement of our stars and bars; $| \star \star | \star | \star \star \star \star \star \star \star \star | \star$ The question mandates that no two bars sit next to each other. Thus, we have 13 "slots" where the bars could go (eleven between the stars, two at the endpoints), where only one bar can fit in each slot. It follows that the number of ways to insert these bars is $_{13} C_4 = 715$ .

Then the probability that Auntie Em cannot park is $\frac{715}{1820} = \frac{11}{28}$ . Finally, our answer is $1-\frac{11}{28} = \frac{17}{28}$ . $\square$

@@ Line 36: / Line 36: @@
 ''[[2008 AMC 12B Problems/Problem 22 | 2008 AMC 12B Problem 22]]: A parking lot has 16 spaces in a row. Twelve cars arrive, each of which requires one parking space, and their drivers chose spaces at random from among the available spaces. Auntie Em then arrives in her SUV, which requires 2 adjacent spaces. What is the probability that she is able to park?''
-'''Solution''': Use complementary probability, where we find the probability that no two open spots are consecutive. With no restrictions, the total number of ways the 12 cars could park is <math>_{16} C_12 = 1820</math>. Finding how many permutations of the cars and spaces leave no two spaces next to each other is a more challenging task, though.
+'''Solution''': Use complementary probability, where we find the probability that no two open spots are consecutive. With no restrictions, the total number of ways the 12 cars could park is <math>_{16} C_{12} = 1820</math>, where <math>_n C_k</math> is a [[combination]]. Finding how many permutations of the cars and spaces leave no two spaces next to each other is a more challenging task, though.
-One might eventually think to treat this problem like a distribution, a [[stars-and-bars]] approach. Let the 12 cars be stars and the 4 spaces be bars. Here's one arrangement of our stars and bars; <cmath>| \star \star | \star | \star \star \star \star \star \star \star \star | \star</cmath> The question mandates that no two bars sit next to each other. Thus, we have 13 "slots" where the bars could go (eleven between the stars, two at the endpoints), where only one bar can fit in each slot. It follows that the number of ways to insert these bars is <math>_{13} C_4 = 715</math>, where <math>_n C_k</math> is a [[combination]].
+One might eventually think to treat this problem like a distribution, a [[stars-and-bars]] approach. Let the 12 cars be stars and the 4 spaces be bars. Here's one arrangement of our stars and bars; <cmath>| \star \star | \star | \star \star \star \star \star \star \star \star | \star</cmath> The question mandates that no two bars sit next to each other. Thus, we have 13 "slots" where the bars could go (eleven between the stars, two at the endpoints), where only one bar can fit in each slot. It follows that the number of ways to insert these bars is <math>_{13} C_4 = 715</math>.
 Then the probability that Auntie Em cannot park is <math>\frac{715}{1820} = \frac{11}{28}</math>. Finally, our answer is <math>1-\frac{11}{28} = \frac{17}{28}</math>. <math>\square</math>

Page

Toolbox

Search