2018 AMC 10A Problem 18

P16-20~4 minPrint

Bases & Digits Basic Counting Map the objects to something easier to count Exploit symmetry to reduce work or pair up objects

How many nonnegative integers can be written in the form $a_7\cdot3^7+a_6\cdot3^6+a_5\cdot3^5+a_4\cdot3^4+a_3\cdot3^3+a_2\cdot3^2+a_1\cdot3^1+a_0\cdot3^0,$ where $a_i\in \{-1,0,1\}$ for $0\le i \le 7$ ?

Show solution without answering

Key insight

Digits -1, 0, 1 with powers of 3 make every whole number from -3280 to 3280 exactly once; the nonnegative ones are 0 through 3280.

Solution

There are $8$ digits, each with $3$ choices, so $3^8 = 6561$ digit strings. We need to know which numbers they make.

1. Try a small case first. With only two digits, $a_1 \cdot 3 + a_0$ , the nine strings give
$-4, -3, -2, -1, 0, 1, 2, 3, 4.$
Nine strings, nine different numbers, and they fill the whole run from $-4$ to $4$ with no gaps. Of these, $0, 1, 2, 3, 4$ are nonnegative: $5$ numbers.
2. Largest and smallest with $8$ digits. The largest value uses all $1$ s:
$1 + 3 + 9 + 27 + 81 + 243 + 729 + 2187 = 3280.$
The smallest uses all $-1$ s and gives $-3280$ .
3. Different strings give different numbers. Suppose two strings gave the same number. Find the lowest position where their digits differ. Subtract the two numbers: the positions below it cancel, that position leaves $1$ or $2$ times its power of $3$ , and every higher position leaves a multiple of the next power of $3$ . A number like $1 \cdot 3^k$ or $2 \cdot 3^k$ plus a multiple of $3^{k+1}$ is never $0$ , so the two numbers were not equal after all.
4. So every number in the run is hit. From $-3280$ to $3280$ there are $3280 + 1 + 3280 = 6561$ whole numbers. We have $6561$ strings making $6561$ different numbers, all inside that run, so every whole number from $-3280$ to $3280$ appears exactly once.
5. Count the nonnegative ones. They are $0, 1, 2, \dots, 3280$ , which is $3281$ numbers.

The answer is $\boxed{\textbf{(D)}\ 3281}$ .

Why this works

This is like ordinary base $3$ , except the digits are $-1, 0, 1$ instead of $0, 1, 2$ . Just as in ordinary base $3$ , each string names a different number. Switching the sign of every digit switches the sign of the number, so the values are balanced around $0$ : equal numbers of positive and negative values, plus $0$ once. That gives $\dfrac{6561 + 1}{2} = 3281$ .

Alternative approach

Build the pattern from small cases. One digit gives $-1, 0, 1$ : $2$ nonnegative. Two digits give $-4$ to $4$ : $5$ nonnegative. Three digits give $-13$ to $13$ : $14$ nonnegative. Each count is $\dfrac{3^k + 1}{2}$ for $k$ digits ( $\tfrac{3+1}{2}$ , $\tfrac{9+1}{2}$ , $\tfrac{27+1}{2}$ ), so $8$ digits give $\dfrac{6561 + 1}{2} = 3281$ .

Concise solution

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

There are $3^8 = 6561$ choices of the digit string $(a_7, \dots, a_0)$ . Two facts settle the count.

All $6561$ sums are distinct. Suppose two different strings gave the same value. Subtracting, we get $\sum (a_i - b_i) 3^i = 0$ with each $a_i - b_i \in \{-2, -1, 0, 1, 2\}$ and not all zero. Look at the smallest index $k$ with $a_k \ne b_k$ : every other nonzero term is a multiple of $3^{k+1}$ , while $(a_k - b_k)3^k$ is not, so the total cannot be $0$ . Contradiction.

The values are symmetric about $0$ . Negating every digit negates the sum, so the set of attainable values is closed under $x \mapsto -x$ . The largest value is $1 + 3 + \dots + 3^7 = \dfrac{3^8 - 1}{2} = 3280$ , so the $6561$ distinct values are exactly $-3280, -3279, \dots, 3279, 3280$ (that is $6561$ consecutive integers, so nothing is skipped).

The nonnegative ones are $0, 1, \dots, 3280$ : that is $3281$ integers.

The answer is $\boxed{\textbf{(D)}\ 3281}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 8: Base Numbers
Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)