Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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 09:10, 2 August 2024

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2010_Problems/Problem_5&oldid=224212"