Mock AIME 1 2010 Problems/Problem 5
Problem
For every integer , the
representation of
is defined to be the unique sequence of integers
, with
and
such that
. We represent
as
, where
if
is 0 or 1, and
if
. For example,
. Find the last three digits of the sum of all integers
with
such that
has at least one zero when written in balanced ternary form.
Solution
Note that , so any number with a maximum term of
or below is a valid value for
, but any number with a maximum value of
needs to have its next highest term (if it exists) be negative, lest it exceed
and thereby become an invalid value of
. The maximum term clearly cannot exceed
.
To make the problem easier, we shall use complementary counting. Thus, we are looking for the values of which, from their maximum terms downwards, do not omit any powers of three
. For
, we need the maximum term to be positive. If that term is
, then we have
possibility, and thus a total sum of
. If the max term is
, 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
. Likewise, for
, we have
possibilities
with sum
. For
, we have
possiblities with sum
. However, for
, as discussed in the first paragraph, we need the
term to be negative, but the remaining
terms can be either sign. Thus, the sum of the possibilities is
, because the
terms do not switch sign and thereby do not cancel out. Therefore, the sum of the values of
without a
in their balanced ternary representation is
.
To find the sum of the values of with a
in their balanced ternary representation, we subtract this sum from the sum of all possible values of
. This larger sum is the
st triangular number, which is
. Subtracting
from this sum, we get
, so our answer is
.
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 |