AMC 10 · 2015 · #18

Grade 7 arithmetic
Archetype Branching State Enumeration └ Sub-archetype Ordered Placement Count
base-conversionsystematic-enumeration casework ↑ Prerequisites: base-conversion
📏 Medium solution 💡 3 insights
Problem
In base 16 (hexadecimal), each place uses one of the symbols 0–9 or A–F (where A,…,F stand for 10,…,15). Look at the integers from 1 to 1000. Count how many of them, when written in hexadecimal, use only the numeric symbols 0–9 (no letter symbols at all). Call that count n, then add up the digits of n.

Pick an answer.

(A)
17
(B)
18
(C)
19
(D)
20
(E)
21

AMC 10 2015 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve
Strategy Make a Systematic List

Listing all 1000 numbers would be hopeless, so instead we count by digit positions (Tool #2): a qualifying number is just a string of hex digits where each position is restricted to 0–9. To set the size of that string we first solve the easier sub-question 'what is 1000 in hex?' (Tool #9), which tells us we only ever deal with 3 hex positions. We break the count into one subproblem per position (Tool #7), and the only delicate part — how large the leading (256's) digit may be — is settled with a boundary check (Tool #14): 4 × 256 = 1024 already passes 1000. Multiplying the per-position choices gives the count directly, no exhausting list needed.

1STEP 1

Convert 1000 to hexadecimal

Repeated division by 16 converts 1000 to 3E8₁₆, so every number 1–1000 has at most three hex digit positions.

1000 = 3 · 16² + 14 · 16 + 8 = 3E8₁₆
2STEP 2

Restate the condition per digit

Writing the number as d₂d₁d₀, the numeric-only condition just restricts each digit to 0–9, never A–F.

d₂ d₁ d₀₁₆ = 256 d₂ + 16 d₁ + d₀, d₂,d₁,d₀ ∈ {0,…,9}
3STEP 3

Bound the leading digit

Checking the extreme case shows d₂ = 4 already exceeds 1000, so d₂ can only be 0–3 (4 choices).

4 · 256 = 1024 ＞ 1000, 399₁₆=921 ≤ 1000
4STEP 4

Multiply the per-digit choices

Multiplying the per-digit choices gives 4 × 10 × 10 = 400 strings; dropping the all-zero one leaves n = 399.

n = 4 × 10 × 10 - 1 = 400 - 1 = 399
5STEP 5

Add the digits of n

Summing the digits of 399 gives 3 + 9 + 9 = 21, which is choice (E).

3 + 9 + 9 = 21 → (E)
Answer
21
n = 4 × 10 × 10 − 1 = 399, digit sum 3 + 9 + 9 = 21
Sanity-check the count. The all-numeric hex strings from 001₁₆ up to 399₁₆ behave exactly like ordinary three-digit decimals 001 through 399 — same symbols, same ordering — so there should be 399 of them, matching n = 399. The cutoff also lines up: 399₁₆ = 921 is the largest qualifying value, and the very next candidates 922, …, 1000 are 39A₁₆, …, 3E8₁₆, all of which contain a letter — so nothing is lost between 921 and 1000. Finally 3+9+9 = 21 is a clean digit sum, and 21 is one of the offered choices.
💡Key takeaway

Count digit slots instead of listing numbers: 4 ways for the first hex digit, 10 for each of the next two, multiply, then drop zero.

  • Convert 1000 to hexadecimal
  • Restate the condition per digit
  • Bound the leading digit
  • Multiply the per-digit choices
  • Add the digits of n

More like this

Same archetype — closest grade level first.