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 \(\dfrac {1} {2}\times \dfrac {1} {2}\times \dfrac {1} {2}=\dfrac {1} {8}\)chance to get all tails = no heads, so if we want at least one head, the answer is 1 - \(\dfrac {1} {8}\)= \(\dfrac {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-\(\dfrac {11} {16}\) ; #2-\(\dfrac {3} {4}\) ; #3- \(\dfrac {7} {8}\) ; #4-\(\dfrac {191} {256}\) #5: 200

Problem Solving Strategies: Applications of the “Choose 2” method

1. Example: How many diagonals can be drawn for a polygon with “n” sides?

Method I:

The number of diagonals in a polygon = n(n-3)/2, where n is the number of polygon sides.

For a convex n-sided polygon, there are n vertexes, and from each vertex you can draw n-3 diagonals, so the total number of diagonals that can be drawn is n (n-3).

However, this would mean that each diagonal would be drawn twice, (to and from each vertex), so the expression must be divided by 2.

Method II:

nC2 (choose 2) - n sides = n(n-1)/ 2 – n sides


2. Example: There are n people at a party, each person shakes hands with the every other person once. How many handshakes?

Method I:
nC2 in this case (10 x 9) /2 =45
__ __ First slot you have 10 persons to choose from, second slot 9 persons. Since A shakes hands with B is the same as B shakes hands with A, so you divide the number by 2 and get the answer.

Method II:
Sum of the first consecutive Natural numbers: n (n+1) /2
The first person shakes hands with 9 other person; the second person shakes hands with 8 other person, etc…
So 9 + 8 + 7 + …= (9 x 10)/ 2 = 45

3. Example: N dots evenly spaced on a circle. How many chords can you make using those dots?

Methods: This is very similar to hand-shaking questions.

I: nC2

II: Sum of the first consecutive (N-1) Natural numbers

Word problems: Answers below.

#1 : A convex polygon with n sides has 20 diagonals. How many diagonals does an (n+1)-sided convex polygon have?

#2: A polygon has n sides and n diagonals. What is n? 

#3: How many diagonals does a decagon have?

#4: How many diagonals does a dodecagon have? 

#5: How many line segments have both their endpoints located at the vertexes of a given cube?

#6: There are 8 points on a circle, how many lines can you make? How many triangles can you make?

#7: If each of the interior angles of two regular polygons adds up to 255 degrees and their diagonals add up to 29, what is the sum of their sides?

Answers: 

# 1- 27    #2 -5     #3-35      #4-54 [12C2 -12]     #5 28 [There are 8 vertices, so 8C2]



#6  8C2 = 28 for lines and 8C3 = 56 triangles   

#7: 6[hexagon] + 8[octagon] = 14 sides