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}$.

See Also

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