2015 AMC 10A Problem 18

P16-20~5 minPrint

Bases & Digits Basic Counting Bound the quantity above/below or estimate to pin it down Set up the equation/formula and compute; no special trick needed

Hexadecimal (base-16) numbers are written using numeric digits $0$ through $9$ as well as the letters $A$ through $F$ to represent $10$ through $15$ . Among the first $1000$ positive integers, there are $n$ whose hexadecimal representation contains only numeric digits. What is the sum of the digits of $n$ ?

Show solution without answering

Key insight

In base 16, 1000 is 3E8. Every three-digit string of digits 0 to 9 starting with 0 to 3 is below it: 400 strings, minus zero.

Solution

First see how big $1000$ is in base $16$ , then count the numbers written with only the digits $0$ to $9$ .

1. Write $1000$ in base 16. The place values are $1$ , $16$ and $16^2 = 256$ . Since $3 \times 256 = 768$ and $4 \times 256 = 1024$ is too big, the first digit is $3$ . What is left is $1000 - 768 = 232 = 14 \times 16 + 8$ . Fourteen is the digit $E$ , so
$1000 = 3E8_{16}.$
2. So every number from $1$ to $1000$ has at most three base-16 digits, and a three-digit one starts with $1$ , $2$ or $3$ .
3. Count the digit strings. Think of every number as three digits, with leading zeros if needed (like $0\,4\,7$ ). We want strings that use only $0$ to $9$ :
- first digit: $0, 1, 2$ or $3$ ( $4$ choices), since $4$ or more is already past $1000$ ;
- second digit: $0$ to $9$ ( $10$ choices);
- third digit: $0$ to $9$ ( $10$ choices).

That is $4 \times 10 \times 10 = 400$ strings.
4. Are they all at most 1000? The biggest one is
$399_{16} = 3 \times 256 + 9 \times 16 + 9 = 921,$
which is less than $1000$ . So yes, all of them.
5. One string is $000$ , which is the number $0$ . It is not a positive integer, so take it away: $n = 400 - 1 = 399$ .
6. The question asks for the sum of the digits of $n$ : $3 + 9 + 9 = 21$ .

The answer is $\boxed{\textbf{(E)}\ 21}$ .

Why this works

Counting numbers with only certain digits is a multiplication count, one factor per digit place. The upper limit is the tricky part: write the limit in the same base, and check whether the biggest allowed string is under it. Here it is ( $921 < 1000$ ), so no extra cases are needed. Also watch the two small details at the end: remove zero, and answer the digit sum, not $n$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

First locate $1000$ in hexadecimal: $1000 = 3 \cdot 256 + 14 \cdot 16 + 8$ , so $1000 = 3E8_{16}$ . Every integer from $1$ to $1000$ has at most three hex digits, with leading digit at most $3$ .

Now count hex strings $d_2 d_1 d_0$ (leading zeros allowed) using only digits $0$ through $9$ whose value is at most $1000$ . The leading digit $d_2$ must be $0, 1, 2$ or $3$ , since $4$ would give at least $4 \cdot 256 = 1024 > 1000$ . If $d_2 \le 3$ and the other digits are at most $9$ , the largest such number is $399_{16} = 3 \cdot 256 + 9 \cdot 16 + 9 = 921 < 1000$ , so every one of these strings is in range.

That gives $4 \cdot 10 \cdot 10 = 400$ strings, one of which is $000$ , representing $0$ , which is not a positive integer. Hence $n = 399$ , and its digit sum is $3 + 9 + 9 = 21$ .

The answer is $\boxed{\textbf{(E)}\ 21}$ .

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 9: Base Number Arithmetic
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques