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 |