Difference between revisions of "Complementary counting"
Etmetalakret (talk | contribs) |
Etmetalakret (talk | contribs) |
||
| Line 24: | Line 24: | ||
Putting these two together, there are <math>16384 - 2916 = 13486</math> ways she can color the seven houses four colors if at least one pair of consecutive houses must be the same color. <math>\square</math> | Putting these two together, there are <math>16384 - 2916 = 13486</math> ways she can color the seven houses four colors if at least one pair of consecutive houses must be the same color. <math>\square</math> | ||
| + | |||
| + | === Example 4 === | ||
| + | ''[[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> | ||
| + | |||
==Video== | ==Video== | ||
| Line 30: | Line 36: | ||
=== Introductory === | === Introductory === | ||
| − | |||
| − | |||
* [[2008 AMC 12B Problems/Problem 22 | 2008 AMC 12B Problem 22]] | * [[2008 AMC 12B Problems/Problem 22 | 2008 AMC 12B Problem 22]] | ||
Revision as of 16:24, 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 
is a subset of 
, complementary counting exploits the property that 
, where 
is the complement of . In most instances, though, is obvious from context.
Contents
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 
are not a multiple of five?
Solution: We use a complementary approach. The total number of positive integers, with no restrictions, is 
integers. What we don't want are the multiples of five; these are 
or 
, so there are 
multiples of five. Thus, our answer is is 
. 
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 
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; 
and 
. 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 
. Hence, our final answer is 
, as desired.
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 
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 
possibilities if every house must be a different color.
Putting these two together, there are 
ways she can color the seven houses four colors if at least one pair of consecutive houses must be the same color.
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 
, where 
and 
are relatively prime positive integers. Find 
Solution: If you're unfamiliar with probability, don't worry; we can turn this into a counting problem, as
\[P(what we want happening) = \frac{# \textrm{possibilities we want}}{#\ textrm{total possibilities}}\] (Error compiling LaTeX. Unknown error_msg)
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
