Difference between revisions of "Complementary counting"

Line 2: Line 2:
  
 
More formally, if <math>B</math> is a [[subset]] of <math>A</math>, complementary counting exploits the property that <math>|B| = |A| - |B^c|</math>, where <math>B^c</math> is the [[complement]] of <math>B</math>. In most instances, though, <math>A</math> is obvious from context.
 
More formally, if <math>B</math> is a [[subset]] of <math>A</math>, complementary counting exploits the property that <math>|B| = |A| - |B^c|</math>, where <math>B^c</math> is the [[complement]] of <math>B</math>. In most instances, though, <math>A</math> is obvious from context.
 +
 +
== Complementary Probabilitiy ==
 +
There is a [[probability]] equivalent of complementary counting. We know that for any event, the probability it happens plus the probability it doesn't happen is one (as either must happen). Thus, we have the identity <cmath>P(A) = 1 - P(A^c).</cmath> Like its counting analog, complementary probability often vastly simplifies tedious casework.
  
 
== Examples ==
 
== 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.
+
Here are some problems where complementary counting and probability are particularly effective. Other solution methods exist for some of these problems, but they are more convoluted than a complementary approach.
  
 
=== Example 1 ===
 
=== Example 1 ===
Line 28: Line 31:
 
''[[2002 AIME I Problems/Problem 1 | 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 <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n.</math>''
 
''[[2002 AIME I Problems/Problem 1 | 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 <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n.</math>''
  
'''Solution''': If you're unfamiliar with probability, don't worry; we can turn this into a counting problem, as <cmath>P(what we want happening) = \frac{# \textrm{possibilities we want}}{#\ textrm{total possibilities}}</cmath>
+
'''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 <math>\frac{9}{10}</math>, and for the letters, it is <math>\frac{25}{26}</math>. Multiplying these together gives that the probability that a license plate has no palindromes is <cmath>\frac{9}{10} \cdot \frac{25}{26} = \frac{225}{260} = \frac{45}{52}.</cmath> Taking the complement of this, the probability a license plate has a palindrome is thus <math>1 - \frac{45}{52} = \frac{7}{52}</math>. Hence, our answer is <math>7 + 52 = 59</math>. <math>\square</math>
  
 +
=== Example 5 ===
 +
''[[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.
 +
 +
One might think to distribute the spots among the cars, a stars-and-bars approach. Let the 12 cars be stars and the 4 spaces be bars, and the arrangement looks like this <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]].
 +
 +
Then the probability that Auntie Em cannot park is <math>\frac{715}{1820} = \frac{11}{28}</math>. Thus, our answer is <math>1-\frac{11}{28} = \frac{17}{28}</math>, and we're done. complement of this is <math>\frac{17}{28}</math>, which is the answer. <math>\square</math>
  
 
==Video==
 
==Video==
Line 37: Line 48:
 
=== Introductory ===
 
=== Introductory ===
 
* [[2008 AMC 12B Problems/Problem 22 | 2008 AMC 12B Problem 22]]
 
* [[2008 AMC 12B Problems/Problem 22 | 2008 AMC 12B Problem 22]]
 
=== Intermediate ===
 
* [[2004 AIME I Problems/Problem 15]]
 
  
 
== See also ==
 
== See also ==

Revision as of 17:39, 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.

Complementary Probabilitiy

There is a probability equivalent of complementary counting. We know that for any event, the probability it happens plus the probability it doesn't happen is one (as either must happen). Thus, we have the identity \[P(A) = 1 - P(A^c).\] Like its counting analog, complementary probability often vastly simplifies tedious casework.

Examples

Here are some problems where complementary counting and probability are 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$

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$. 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 think to distribute the spots among the cars, a stars-and-bars approach. Let the 12 cars be stars and the 4 spaces be bars, and the arrangement looks like this \[| \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$, where $_n C_k$ is a combination.

Then the probability that Auntie Em cannot park is $\frac{715}{1820} = \frac{11}{28}$. Thus, our answer is $1-\frac{11}{28} = \frac{17}{28}$, and we're done. complement of this is $\frac{17}{28}$, which is the answer. $\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

See also