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.