Problem Solving Strategy: Complementary Counting

#: How many three digit numbers contain the digit "9" at least once?
Solution:
For the "at least" questions: a lot of the time, the easiest way to solve the problems is to use the total number of ways minus the number of ways which do not satisfy the criteria we're looking for.

There are 999 -100 + 1 = 900 three digit numbers.

There are 8 x 9 x 9 = 648 numbers that do not contain the digit "9" at all, so the answer is 900 - 648 = 252

#2: How many three digit numbers have at least two digits that are the same? 
Solution:
Use complementary counting to find how many three digit numbers have no digit that are the same.
9 digit choices for the hundredth digit (no 0), 9 for the tenth digit (0 is allowed) and 8 digit left for the unit digit, so 9 * 9 * 8 = 648
900 (3 digit numbers) - 648 = 252  

#3: How many of the natural numbers from 1 to 600, inclusive, contain the digit "5" at least once?
(The numbers 152 and 553 are two natural numbers that contain the digit 5 at least once, but 430 is not.)
Solution: 
From 1 to 600 inclusive, there are 600 - 1 + 1 = 600 numbers.

___ ___ ___ If we're looking for all the three-digit numbers which do not contain any 5s: In the hundreds place, you can put 0, 1, 2, 3, or 4 (we'll get rid of '000' later). In the tens place, you can put 9 digits, and there are another 9 possible digits for the units digit, so 5 x 9 x 9 = 405.

405 - 1 (to get rid of '000') + 1 (to compensate for not counting the number '600') = 405, which is the total number of numbers which don't use the digit '5'.

600 - 405 =195, which is the answer.

#4: If you toss three coins, what is the probability that at least one coin lands heads up? 
Solution:
There is a ${\displaystyle \frac{1}{2}}\times {\displaystyle \frac{1}{2}}\times {\displaystyle \frac{1}{2}}={\displaystyle \frac{1}{8}}$chance to get all tails = no heads, so if we want at least one head, the answer is 1 - ${\displaystyle \frac{1}{8}}$= ${\displaystyle \frac{7}{8}}$.

Other applicable problems (answers below):
#1: Amy tosses a nickel four times. What is the probability that she gets at least as many heads as tails ?
#2: What is the probability that the product of the top faces on 2 standard die is even when rolled?
#3: 3 numbers are selected at random, with replacement, from the set of integers from 1 to 600 inclusive. What is the probability that the product of the 3 numbers is even ? Express your answer as a common fraction in lowest terms.
#4: 9 fair coins are flipped. What is the probability that at least 4 are heads? 
#5: How many 3 digit numbers does not contain the digit 1 but have at least one digit that is 5?







Answer: #1-${\displaystyle \frac{11}{16}}$ ; #2-${\displaystyle \frac{3}{4}}$ ; #3- ${\displaystyle \frac{7}{8}}$ ; #4-${\displaystyle \frac{191}{256}}$ #5: 200

Problem Solving Strategies : Complementary Counting

Check out Mathcounts here, the best competition math program for middle school students.

Download this year's Mathcounts handbook here.

Video to watch on complementary counting from "Art of Problem Solving"

Part 1

Part 2

Question: How many two-digit numbers contain at least one 9?

 At beginning level, kids start to write down all the numbers that contain 9. However, this turns into impossible task if it's a three-digit or four-digit number. So let's try other ways to do it.

9 _ , if 9 is placed as the tens digit, unit digit can be chosen from 0 -9, altogether 10 numbers.
A lot of kids think there are only 9. Be careful. To find how many consecutive terms from number a to b, you do (b-a) +1

_ 9, there will be 9 choices (1-9) this time as the tens digit.(Why?) Zero can't be placed other than unit digit.
So total you have 10 + 9 - 1 (you've counted 99 twice) = 18

This way is better than the first one, but once the numbers become large, you will easily lose track of those double-counting, triple-counting numbers and over count your answers.

Here is a better way to tackle this type of problem: Think about the case of numbers that contain no 9s, and subtracting this value from the total number of two-digit numbers will give you the answer.

There are 99-10 +1 =90 total two digit numbers. There are 8 (the tens digit) x 9 (unit digit) = 72 numbers that contain no 9s. So 90-72 = 18 gives you the answer.

Try this question: 
How many three-digit numbers contain at least one 9?
There are 999 - 100 + 1 or 999 - 99 = 900 three-digit numbers. 
Or 9 x 10 (you can use the digit "0" now" x 10 = 900 three-digit numbers
900 - 8 x 9 x 9 = 252 numbers 

This is called "complementary counting" and there are numerous problems that you can use this strategies to simplify the reasoning. 

Here is another harder problem from 2003 Mathcounts Chapter Sprint Round #29:
Each day, two out of the three teams in a class are randomly selected to participate in a MATHCOUNTS trial competition. What is the probability that Team A is selected on at least two of the next three days? Express your answer as a common fraction.

Solution:  
Use complementary counting. 
If each day two of the team will be chosen, there will be 3C2 = 3 ways to choose the team -- AB, BC, or AC, so 1/3 of the chance that team A won't be chosen and 2/3 of the chance that team A will be chosen. 

Case 1: Team A is not chosen on any of the three days. The probability is (1/3) ³= 1/27.
Case 2: Team A is chosen on one of the three days : The probability is (2/3) times (1/3)² times 3C1 = 6/27 (A - -, - A - or - - A, which is 3C1 = 3 ways)

Total possibilities - none - at least 1 time = at least two times Team A will be chosen 
so the answer is 1 - 1/27 - 6/27 = 20/27

Other applicable problems: (answer key below)

#1: 2006 AMC10 A: How many four-digit positive integers have at least one digit that is a 2 or 3? 

#2: What is the probability that when tossing two dice, at least one dice will come up a "3"? 

#3: If {x,y} is a subset of S={1,2,3,....50}. What is the probability that xy is even?















Answer key: 

#1:  9000 - 7 x 8 x 8 x 8 = 5416

#2:  The probability of the dice not coming up with a "3" is 5/6.
       1 - (5/6)² = 11/36

2. 1 - (25/50) (24/49) -- only odd times odd will give you odd product, the others will all render even product, so the answer is 37/49.