How many three-digit numbers are not divisible by , have digits that sum to less than , and have the first digit equal to the third digit?
- A)
- B)
- C)
- D)
- E)
Answer
B
Key insight
The number is aba with a not 5. Small a allows every middle digit b; for a from 6 to 9, b must be below 20 - 2a.
Solution
- What the numbers look like. The first and last digits are the same, so the number is , like or . Here is to and is to .
- Not divisible by 5. A number is divisible by when it ends in or . It ends in , and is never , so we just need .
- Digit sum less than 20. The digits add to , and we need , so .
- Go through the values of .
| must be less than | allowed | how many | |
|---|---|---|---|
| 1, 2, 3, 4 | 18 or more | all of 0 to 9 | 10 each, so 40 |
| 5 | (not allowed) | — | 0 |
| 6 | 8 | 0 to 7 | 8 |
| 7 | 6 | 0 to 5 | 6 |
| 8 | 4 | 0 to 3 | 4 |
| 9 | 2 | 0, 1 | 2 |
For small the biggest possible sum is , which is already under , so every works.
5. Add. .
The answer is .
Why this works
The "first digit equals last digit" rule leaves only two digits to choose. Each other rule then limits one of them. Going through one value at a time makes the digit-sum rule easy: it never matters for small , and for large the counts drop by each time.
Alternative approach
Count the bad ones and subtract. There are numbers of the form . Take away the with , leaving . The ones with digit sum or more need : that is numbers for , or in all. So .
The trap
Forgetting that a number ending in 5 is divisible by 5, so a = 5 must be left out. Keeping it adds 10 numbers and gives 70.
Concise solution
Write the number as with and . The last digit is , so "not divisible by " means (and , already excluded). The digit sum condition is .
Case : , so all values of work: numbers.
Case : need , so : numbers.
Case : need : numbers.
Case : need : numbers.
Case : need : numbers.
Total: .
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 Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)
Techniques
Split into exhaustive cases and handle each