2017 AMC 10B Problem 16
How many of the base-ten numerals for the positive integers less than or equal to contain the digit ?
Show solution without answering
Key insight
Count the numbers with no 0, where every digit is 1 to 9: 9 + 81 + 729 + 729 = 1548. The other 469 contain a 0.
Solution
A number can contain one or several, which makes direct counting messy. It is much easier to count the numbers with no and subtract from .
A number with no uses only the digits to , so each place has choices. Count by the number of digits:
- One-digit numbers ( to ): .
- Two-digit numbers: .
- Three-digit numbers: .
- Four-digit numbers from to : the first digit is , and the other three places have choices each: .
- Four-digit numbers from to : every one has a in the hundreds place, so none of them count here.
- Numbers with no : .
- Numbers with at least one : .
The answer is .
Why this works
"At least one" is often hard to count directly because of the many ways it can happen; "none" is usually a simple multiplication. Splitting by the number of digits keeps the first digit from being , and the odd little tail to is easiest to check by hand.
Concise solution
A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.
Count the complement: integers from to with no digit equal to . Each digit can then be any of through .
- One-digit numbers: .
- Two-digit numbers: .
- Three-digit numbers: .
- Four-digit numbers from to : leading digit , then choices for the rest.
- Four-digit numbers from to : every one has a in the hundreds place, so zero-free numbers.
Zero-free total: .
Numbers containing a : .
The answer is .
Review in the AoPS books
- Introduction to Number Theory, Chapter 8: Base Numbers
- Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.3)
- Introduction to Number Theory, Chapter 9: Base Number Arithmetic
Similar problems
Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.