Mock AIME 1 2010 Problems/Problem 5

Problem

For every integer $N$ , the $\emph{balanced ternary}$ representation of $N$ is defined to be the unique sequence of integers $(b_0, b_1, \ldots, b_m)$ , with $b_i \in \{-1, 0, 1\}$ and $b_m \neq 0$ such that $N = \sum_{i=0}^{m} b_i 3^i$ . We represent $N$ as $c_0 c_1 \ldots c_m$ , where $c_i = b_i$ if $b_i$ is 0 or 1, and $c_i = \underline{1}$ if $b_i = -1$ . For example, $2010 = 3^7 - 3^5 + 3^4 - 3^3 + 3^2 + 3 = 10\underline{1}1\underline{1}110$ . Find the last three digits of the sum of all integers $N$ with $1 \leq N \leq 81$ such that $N$ has at least one zero when written in balanced ternary form.

Solution

Note that $3^3+3^2+3^1+3^0=40<81$ , so any number with a maximum term of $3^3$ or below is a valid value for $N$ , but any number with a maximum value of $3^4$ needs to have its next highest term (if it exists) be negative, lest it exceed $81$ and thereby become an invalid value of $N$ . The maximum term clearly cannot exceed $3^4$ .

To make the problem easier, we shall use complementary counting. Thus, we are looking for the values of $N$ which, from their maximum terms downwards, do not omit any powers of three $\geq 3^0$ . For $N>0$ , we need the maximum term to be positive. If that term is $3^0$ , then we have $1$ possibility, and thus a total sum of $1$ . If the max term is $3^1$ , then we have two possibilities, because the second term can be either plus or minus. The plus and minus terms cancel out, so the sum of these possibilities is $2\cdot3^1=6$ . Likewise, for $3^2$ , we have $2^2=4$ possibilities $(3^2 \pm 3^1 \pm 3^0)$ with sum $4\cdot3^2=36$ . For $3^3$ , we have $2^3=8$ possiblities with sum $8\cdot3^3=216$ . However, for $3^4$ , as discussed in the first paragraph, we need the $3^3$ term to be negative, but the remaining $2^3=8$ terms can be either sign. Thus, the sum of the possibilities is $8(3^4-3^3)=8(54)=432$ , because the $3^3$ terms do not switch sign and thereby do not cancel out. Therefore, the sum of the values of $N$ without a $0$ in their balanced ternary representation is $1+6+36+216+432=43+648=691$ .

To find the sum of the values of $N$ with a $0$ in their balanced ternary representation, we subtract this sum from the sum of all possible values of $N$ . This larger sum is the $81$ st triangular number, which is $\tfrac{81(82)}2=81\cdot41=3321$ . Subtracting $691$ from this sum, we get $3321-691=2630$ , so our answer is $\boxed{630}$ .

Mock AIME 1 2010 (Problems, Source)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Page

Toolbox

Search

Mock AIME 1 2010 Problems/Problem 5

Problem

Solution

See Also