Difference between revisions of "Mock AIME 1 2010 Problems/Problem 5"
(created solution page) |
(→Solution) |
||
Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
− | <math>\boxed{630}</math>. | + | Note that <math>3^3+3^2+3^1+3^0=40<81</math>, so any number with a maximum term of <math>3^3</math> or below is a valid value for <math>N</math>, but any number with a maximum value of <math>3^4</math> needs to have its next highest term (if it exists) be negative, lest it exceed <math>81</math> and thereby become an invalid value of <math>N</math>. The maximum term clearly cannot exceed <math>3^4</math>. |
+ | |||
+ | To make the problem easier, we shall use [[complementary counting]]. Thus, we are looking for the values of <math>N</math> which, from their maximum terms downwards, do not omit any powers of three <math>\geq 3^0</math>. For <math>N>0</math>, we need the maximum term to be positive. If that term is <math>3^0</math>, then we have <math>1</math> possibility, and thus a total sum of <math>1</math>. If the max term is <math>3^1</math>, 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 <math>2\cdot3^1=6</math>. Likewise, for <math>3^2</math>, we have <math>2^2=4</math> possibilities <math>(3^2 \pm 3^1 \pm 3^0)</math> with sum <math>4\cdot3^2=36</math>. For <math>3^3</math>, we have <math>2^3=8</math> possiblities with sum <math>8\cdot3^3=216</math>. However, for <math>3^4</math>, as discussed in the first paragraph, we need the <math>3^3</math> term to be negative, but the remaining <math>2^3=8</math> terms can be either sign. Thus, the sum of the possibilities is <math>8(3^4-3^3)=8(54)=432</math>, because the <math>3^3</math> terms do not switch sign and thereby do not cancel out. Therefore, the sum of the values of <math>N</math> ''without'' a <math>0</math> in their balanced ternary representation is <math>1+6+36+216+432=43+648=691</math>. | ||
+ | |||
+ | To find the sum of the values of <math>N</math> ''with'' a <math>0</math> in their balanced ternary representation, we subtract this sum from the sum of all possible values of <math>N</math>. This larger sum is the <math>81</math>st [[triangular number]], which is <math>\tfrac{81(82)}2=81\cdot41=3321</math>. Subtracting <math>691</math> from this sum, we get <math>3321-691=2630</math>, so our answer is <math>\boxed{630}</math>. | ||
== See Also == | == See Also == | ||
{{Mock AIME box|year=2010|n=1|num-b=4|num-a=6}} | {{Mock AIME box|year=2010|n=1|num-b=4|num-a=6}} |
Latest revision as of 10:10, 2 August 2024
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 |