AMC 10 · 2005 · #19

Grade 7 counting
Archetype Branching State Enumeration └ Sub-archetype Ordered Placement Count
digit-countingfundamental-counting-principlebase-conversion complementary-countingsystematic-enumeration ↑ Prerequisites: digit-countingfundamental-counting-principleplace-value
📏 Medium solution 💡 2 insights
Problem
A broken odometer never shows the digit 4, stepping straight from 3 to 5 in every position. The display now reads two thousand five. Work out the true mileage.

Pick an answer.

(A)
1404
(B)
1462
(C)
1604
(D)
1605
(E)
1804
How to solve
Strategy Change Focus / Count the Complement

Following the odometer mile by mile is hopeless. Change what is being counted instead: the display advances exactly one step per mile, so the mileage equals the number of allowed displays from 1 up to 002005. An allowed display is just a numeral with no digit 4, and numerals like that can be counted one place at a time.

1STEP 1

Count displays, not miles

The mileage is really a count of allowed numbers.

m = #{ n : 1 ≤ n ≤ 2005, n has no digit 4 }
2STEP 2

Break the range at 2000

Splitting off the last few numbers leaves a uniform range.

{1,…,2005} = {1,…,1999} ∪ {2000,…,2005}
3STEP 3

Count the allowed four-digit strings

Padding with zeros makes each digit an independent choice.

2 × 9 × 9 × 9
4STEP 4

Evaluate and drop the string 0000

Dropping the all-zero string leaves 1457.

2 · 9³ - 1 = 2 · 729 - 1 = 1458 - 1 = 1457
5STEP 5

List the short tail

The short tail contributes 5 more.

2000, 2001, 2002, 2003, 2005 ⟹ 5
6STEP 6

Add the two counts

Adding gives 1462, choice (B).

1457 + 5 = 1462
Answer
1462
Count the skipped numbers instead and see whether the two counts fill the range. Between 1 and 2005 the thousands digit is never 4, so a number is skipped exactly when a 4 appears in the hundreds, tens, or units place. There are 200 numbers with a 4 in the hundreds place, 200 with a 4 in the tens place, and 201 with a 4 in the units place; each pair of those conditions holds together for 20 numbers, and all three hold only for 444 and 1444. Inclusion and exclusion gives 200 + 200 + 201 - 20 - 20 - 20 + 2 = 543 skipped numbers, and 2005 - 543 = 1462, the same answer. The size is also believable: three digit places are free and each survives about nine tenths of the time, and 2005 times 0.9 cubed is about 1462.
💡Key takeaway

A counter that refuses one digit is really counting with nine symbols instead of ten, so count the numerals it is willing to show.

  • Count displays, not miles
  • Break the range at 2000
  • Count the allowed four-digit strings
  • Evaluate and drop the string 0000
  • List the short tail
  • Add the two counts

More like this

Same archetype — closest grade level first.