AMC 8 · 2016 · #17

Grade 4 counting

Archetype Overlap / Complement Counting └ Sub-archetype Complement by Subtracting Forbidden Arrangements

permutations-basiccomplementary-countingsystematic-enumeration complementary-countingsystematic-enumeration ↑ Prerequisites: permutations-basicmulti-digit-arithmetic

📏 Short solution 💡 2 insights

📘 View easy version →

Problem

A password is 4 digits, and each digit is anything from 0 to 9 (repeats are fine). The only rule is that the password is NOT allowed to start with the three digits 9, 1, 1 (in that order). How many passwords are still allowed?

Pick an answer.

(A)

$mbox{ }30$

(B)

$mbox{ }7290$

(C)

$mbox{ }9000$

(D)

$mbox{ }9990$

(E)

$mbox{ }9999$

AMC 8 2016 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve

Strategy Change Focus / Count the Complement

Counting allowed passwords directly is messy — we would have to handle every first-digit case carefully. The forbidden set is much smaller, so Tool #16 (Complement) wins: count ALL 4-digit strings, count just the forbidden ones starting with 9,1,1, and subtract. Tool #2 (Systematic List) is the natural way to confirm the forbidden count — list 9110, 9111, …, 9119 and check we have exactly 10 items.

1STEP 1

Count the whole universe first: 4 positions, 10 choices each, so 10,000 passwords with no rules.

10 × 10 × 10 × 10 = 10,000

2STEP 2

Count the forbidden ones: first three digits pinned to 9, 1, 1 and only the 4th is free, giving 10 banned passwords.

1 × 1 × 1 × 10 = 10

3STEP 3

List them in order to be sure: 9110, 9111, …, 9119 — exactly 10 items, only the last digit varies.

9110, 9111, 9112, 9113, 9114, 9115, 9116, 9117, 9118, 9119 → 10 items

4STEP 4

Subtract forbidden from total — the complement step: 10,000 - 10 = 9,990 allowed passwords (D).

10,000 - 10 = 9,990 → (D)

Answer

mbox{ }9990

Out of 10,000 possible passwords, only 10 are banned — a tiny fraction (0.1%). So the allowed count should be just slightly below 10,000. Choice (D) 9,990 matches that exactly. Choices (A) 30 and (B) 7290 are far too small, and (E) 9999 would mean only 1 forbidden password — but the 4th digit gives 10 forbidden options, not 1. (C) 9000 would correspond to banning every password whose first digit is 9, which is not the rule.

💡Key takeaway

When the "not allowed" cases are few, count those instead and subtract — that's the complement trick, and it only needs Grade 4 multiplication and subtraction.

More like this