Competition · AMC preparation · step 4 of 4

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 all passwords

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

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 to check

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 the forbidden count

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

10,000 - 10 = 9,990 → (D)
Answer
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.

  • Count all passwords
  • Count the forbidden ones
  • List them to check
  • Subtract the forbidden count

A parent dashboard for the family lives at sensimlab.com.

More like this

Same problem type. Tags show what each one shares with this problem.