Skip to content
Mastering
AMC 8
Combinatorics · Chapter 6

Complementary Counting

When "at least one" is hard to count, count the opposite and subtract it from the total.

What's this chapter about?
You'll need
open on YouTube
6.10%

Complementary Counting Fundamentals

In this section you will be able to count the opposite of what you want, then subtract it from the total.

How many 3-digit numbers have at least one 7? Counting numbers with one 7, two 7s and three 7s is a lot of work. Is there a shortcut?

Complementary counting means you count the opposite of what you want, then subtract it from the total:

Look:wanted = all − opposite.

The words “at least” are a big signal. The opposite of “at least one 7” is “no 7 at all”, and that is easy to count.

Exploreplay first, formulas later

All 900 (all 3-digit numbers) − 648 with no 7 at all = 252 with at least one 7

special digit7
digits3
The question asks for:
All: 900 (all 3-digit numbers)
107117127137147157167170171172173174175176177178179187197207217227237247257267270271272273274275276277278279287297307317327337347357367370371372373374375376377378379387397407417427437447457467470471472473474475476477478479487497507517527537547557567570571572573574575576577578579587597607617627637647657667670671672673674675676677678679687697700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799807817827837847857867870871872873874875876877878879887897907917927937947957967970971972973974975976977978979987997100101102103104105106108109110111112113114115116118119120121122123124125126128129130131132133134135136138139140141142143144145146148149150151152153154155156158159160161162163164165166168169180181182183184185186188189190191192193194195196198199200201202203204205206208209210211212213214215216218219220221222223224225226228229230231232233234235236238239240241242243244245246248249250251252253254255256258259260261262263264265266268269280281282283284285286288289290291292293294295296298299300301302303304305306308309310311312313314315316318319320321322323324325326328329330331332333334335336338339340341342343344345346348349350351352353354355356358359360361362363364365366368369380381382383384385386388389390391392393394395396398399400401402403404405406408409410411412413414415416418419420421422423424425426428429430431432433434435436438439440441442443444445446448449450451452453454455456458459460461462463464465466468469480481482483484485486488489490491492493494495496498499500501502503504505506508509510511512513514515516518519520521522523524525526528529530531532533534535536538539540541542543544545546548549550551552553554555556558559560561562563564565566568569580581582583584585586588589590591592593594595596598599600601602603604605606608609610611612613614615616618619620621622623624625626628629630631632633634635636638639640641642643644645646648649650651652653654655656658659660661662663664665666668669680681682683684685686688689690691692693694695696698699800801802803804805806808809810811812813814815816818819820821822823824825826828829830831832833834835836838839840841842843844845846848849850851852853854855856858859860861862863864865866868869880881882883884885886888889890891892893894895896898899900901902903904905906908909910911912913914915916918919920921922923924925926928929930931932933934935936938939940941942943944945946948949950951952953954955956958959960961962963964965966968969980981982983984985986988989990991992993994995996998999
All: 900
We want: at least one 7
Count it directly
3 cases to add
number of 7s: 1, 2, 3
Count the opposite
1 case, then 1 subtraction
number of 7s: 0

All: 900 (all 3-digit numbers)

Name it

Remark 6.1.1

Often you also need this fact together with complementary counting: the number of ways to choose any number of items from nn items is

2n.2^n.

Each item has 2 choices: in the group, or not.

Watch itpredict, then reveal

Example 6.1

I roll 2 fair 6-sided dice. How many ways are there for the sum of the numbers to be 11 or less?

All 36 (all rolls of 2 dice) − 1 with sum more than 11 = 35 with sum 11 or less

sum11
The question asks for:
All: 36 (all rolls of 2 dice)
112233445566223344556677334455667788445566778899556677889910106677889910101111778899101011111212
All: 36
We want: sum 11 or less
Count it directly
10 cases to add
sum: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Count the opposite
1 case, then 1 subtraction
sum: 12

All: 36 (all rolls of 2 dice)

  1. 1

    You could count every sum from 2 to 11, but that is slow. What is the opposite of rolling a sum of 11 or less?

    Predict first:

Example 6.2

Omega Learn

You have 7 slips of paper numbered 1 to 7. How many ways are there to choose any subset of them so that you have at least 2 odd numbers and 1 even number?

  1. 1

    Split the slips into odd and even. How many odd slips are there?

    Predict first:
open on YouTube

Example 6.3

AMC 10

When a certain unfair die is rolled, an even number is 3 times as likely to appear as an odd number. The die is rolled twice. What is the probability that the sum of the numbers rolled is even?

  1. 1

    On one roll, what is the probability of getting an even number?

    Predict first:
open on YouTube

Example 6.4

AIME

A positive integer is called ascending if, in its decimal representation, there are at least two digits and each digit is less than any digit to its right. How many ascending positive integers are there?

  1. 1

    Can an ascending number contain the digit 0?

    Predict first:
open on YouTube

Try it

Problem 6.3.1

If you toss four coins, in how many ways will there be at least 1 head?

Problem 6.3.2

If you toss four coins, in how many ways will there be at least 2 heads?

Problem 6.3.3

How many three digit numbers contain the digit 5 at least once?

Problem 6.3.5

How many ways are there to select a group of 3 people from 5 women and 3 men if there must be at least 1 man in the group?

Contest cornerreal contest problems

Problem 6.3.10

AMC 12

How many subsets of {2,3,4,5,6,7,8,9}\{2, 3, 4, 5, 6, 7, 8, 9\} contain at least one prime number?

Checkpoint for section 6.1

Get 2 of 3 right to master this section. One try each, no hints.
1

How many 2-digit numbers contain at least one 7?

2

How many subsets of {1,2,3,4,5}\{1, 2, 3, 4, 5\} contain at least one even number?

3

Zara has a collection of 4 marbles: an Aggie, a Bumblebee, a Steelie, and a Tiger. She wants to display them in a row on a shelf, but does not want to put the Steelie and the Tiger next to one another. In how many ways can she do this?

6.20%

Complementary Counting with Casework

In this section you will be able to mix complementary counting with casework and probability.

You roll 4 dice. What is the chance that at least one shows a 6? Listing all the ways to get one, two, three or four 6s is painful. The chance of no 6 at all is much easier!

Sometimes even the opposite has a few cases. That’s fine: do casework on the opposite, add the cases, then subtract.

For probability, the same idea reads: the chance of at least one is 1 minus the chance of none.

Exploreplay first, formulas later

1 die: P(at least one 6) = 1 − (5/6)^1 = 1 − 5/6 = 1/6 ≈ 16.7%

number of dice1
?
P(no 6) = (56)1\left(\tfrac{5}{6}\right)^{1}
P(at least one 6) ≈ 16.7%
0%50%100%123456789101112

1 die: P(no 6) = 5/6; P(at least one 6) = 1/6 ≈ 16.7%

Name it

Remark 6.2.1

Oftentimes, you have to use complementary counting together with other ideas, like casework and probability. For probability, the complement rule is

P(at least one)=1−P(none).P(\text{at least one}) = 1 - P(\text{none}).

Watch itpredict, then reveal

Example 6.5

I roll 2 fair 6-sided dice. What is the probability that the sum of the numbers is 5 or more?

All 36 (all rolls of 2 dice) − 6 with sum less than 5 = 30 with sum 5 or more

sum5
The question asks for:
All: 36 (all rolls of 2 dice)
112233445566223344556677334455667788445566778899556677889910106677889910101111778899101011111212
All: 36
We want: sum 5 or more
Count it directly
8 cases to add
sum: 5, 6, 7, 8, 9, 10, 11, 12
Count the opposite
3 cases, then 1 subtraction
sum: 2, 3, 4

All: 36 (all rolls of 2 dice)

  1. 1

    You could do casework on sums 5 to 12, but there's a faster way. What is the opposite of rolling a sum of 5 or more?

    Predict first:

Example 6.6

How many subsets of the set {1,2,3,4,5,6,7,8,9,10}\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} have at least 1 even number and do not contain all of the elements?

  1. 1

    How can you use complementary counting?

Example 6.7

Omega Learn

There are 3 sections of a dart board. The outermost section is worth 2 point if hit. The middle section is worth 5 points if hit. The innermost section is worth 10 points if hit. The probability you hit inner section is 14\frac14, the probability you hit the middle section is 38\frac38, the probability you hit the outermost section is 28\frac28, and the probability you miss the dartboard entirely is 18\frac18. You throw 3 darts at the dartboard. What is the probability you get less than 20 points?

  1. 1

    "Less than 20" has lots of cases. What is the opposite?

    Predict first:
open on YouTube

Try it

Problem 6.3.4

How many 3 digit numbers have at least 2 digits that are the same?

Problem 6.3.7

How many 4 digit numbers are not palindromes? A palindrome is a number that reads the same forward and backward.

Problem 6.3.11

There are 9 different flavors of ice cream at an ice cream shop. Joe wants to buy 2 or 3 scoops of different ice cream flavors. He doesn't like 2 of the flavors Mango and Chocolate together so won't buy them together. How many ways can he buy ice cream?

Contest cornerreal contest problems

Problem 6.3.6

AMC 8

A box contains five cards, numbered 1, 2, 3, 4, and 5. Three cards are selected randomly without replacement from the box. What is the probability that 4 is the largest value selected?

Problem 6.3.9

AMC 8

From a regular octagon, a triangle is formed by connecting three randomly chosen vertices of the octagon. What is the probability that at least one of the sides of the triangle is also a side of the octagon?

Problem 6.3.12(additional)

AMC 10

Una rolls 6 standard 6-sided dice simultaneously and calculates the product of the 6 numbers obtained. What is the probability that the product is divisible by 4?

Checkpoint for section 6.2

Get 2 of 3 right to master this section. One try each, no hints.
1

You roll 2 fair 6-sided dice. What is the probability that the sum is 4 or more?

2

You flip 3 fair coins. What is the probability of getting at least one head?

3

You have 6 identical pears and 5 identical apples. You choose 4 fruits at random. What is the probability of picking at least 1 pear?

6.3

Practice Problems

In this section you will be able to use complementary counting on a mix of contest problems.

Time to mix it up! Each problem below asks for “at least”, “not” or “less than”. Before you count, ask yourself: is the opposite easier?

Want every problem from this chapter on one page? Open the problem set.

Mixed practice

Problem 6.3.14(additional)

There are 10 slips of paper numbered 1 to 5 in a bag, each equally likely to be drawn. You draw a slip, and then immediately put it back in the bag. What is the least number of slips you must draw in order to have at least a 12\frac12 chance of drawing the number 3?

Problem 6.3.15(additional)

You have 6 identical pears and 5 identical apples. You choose 4 fruits at random. What is the probability of picking at least 1 pear?

Contest cornerreal contest problems

Problem 6.3.8

Omega Learn Math Contest

Alice, Bob, Claire, Dave, Emma are sitting around a round table. Alice refuses to sit next to Bob. How many different ways can they sit around the table? (Rotations of the same arrangement are not considered different).

Problem 6.3.13(additional)

AMC 8

Zara has a collection of 4 marbles: an Aggie, a Bumblebee, a Steelie, and a Tiger. She wants to display them in a row on a shelf, but does not want to put the Steelie and the Tiger next to one another. In how many ways can she do this?