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 "2018 AMC 10A Problems/Problem 18"
Line 1: Line 1:
−
== Problem ==
+
==Problem==
 
How many nonnegative integers can be written in the form <cmath>a_7\cdot3^7+a_6\cdot3^6+a_5\cdot3^5+a_4\cdot3^4+a_3\cdot3^3+a_2\cdot3^2+a_1\cdot3^1+a_0\cdot3^0,</cmath>
 
How many nonnegative integers can be written in the form <cmath>a_7\cdot3^7+a_6\cdot3^6+a_5\cdot3^5+a_4\cdot3^4+a_3\cdot3^3+a_2\cdot3^2+a_1\cdot3^1+a_0\cdot3^0,</cmath>
 
where <math>a_i\in \{-1,0,1\}</math> for <math>0\le i \le 7</math>?
 
where <math>a_i\in \{-1,0,1\}</math> for <math>0\le i \le 7</math>?
Line 9: Line 9:
 
\textbf{(E) } 59,048 </math>
 
\textbf{(E) } 59,048 </math>
  
−
==Solution==
+
==Solution 1==
  
 
This looks like balanced ternary, in which all the integers with absolute values less than <math>\frac{3^n}{2}</math> are represented in <math>n</math> digits. There are 8 digits. Plugging in 8 into the formula gives a maximum bound of <math>|x|=3280.5</math>, which means there are 3280 positive integers, 0, and 3280 negative integers. Since we want all nonnegative integers, there are <math>3280+1=\boxed{3281}</math> integers or <math>\boxed{D}</math>.
 
This looks like balanced ternary, in which all the integers with absolute values less than <math>\frac{3^n}{2}</math> are represented in <math>n</math> digits. There are 8 digits. Plugging in 8 into the formula gives a maximum bound of <math>|x|=3280.5</math>, which means there are 3280 positive integers, 0, and 3280 negative integers. Since we want all nonnegative integers, there are <math>3280+1=\boxed{3281}</math> integers or <math>\boxed{D}</math>.
Line 19: Line 19:
 
Note that all numbers formed from this sum are either positive, negative or zero. The number of positive numbers formed by this sum is equal to the number of negative numbers formed by this sum, because of symmetry. There is only one way to achieve a sum of zero, if all <math>a_i=0</math>. The total number of ways to pick <math>a_i</math> from <math>i=1, 2, 3, ... 7</math> is <math>3^8=6561</math>. <math>\frac{6561-1}{2}=3280</math> gives the number of possible negative integers. The question asks for the number of nonnegative integers, so subtracting from the total gives <math>6561-3280=\boxed{3281}</math>. (RegularHexagon)
 
Note that all numbers formed from this sum are either positive, negative or zero. The number of positive numbers formed by this sum is equal to the number of negative numbers formed by this sum, because of symmetry. There is only one way to achieve a sum of zero, if all <math>a_i=0</math>. The total number of ways to pick <math>a_i</math> from <math>i=1, 2, 3, ... 7</math> is <math>3^8=6561</math>. <math>\frac{6561-1}{2}=3280</math> gives the number of possible negative integers. The question asks for the number of nonnegative integers, so subtracting from the total gives <math>6561-3280=\boxed{3281}</math>. (RegularHexagon)
  
−
==Solution 3 (Quick Solution)==
+
==Solution 3==
 
Note that the number of total possibilities (ignoring the conditions set by the problem) is <math>3^8=6561</math>. So, E is clearly unrealistic.  
 
Note that the number of total possibilities (ignoring the conditions set by the problem) is <math>3^8=6561</math>. So, E is clearly unrealistic.  
  
Line 26: Line 26:
 
As A, B, and C are all less than 2187, the answer must be <math>\boxed{(D) 3281}</math>
 
As A, B, and C are all less than 2187, the answer must be <math>\boxed{(D) 3281}</math>
  
−
== Solution 4 ==
+
==Solution 4==
 
Note that we can do some simple casework:
 
Note that we can do some simple casework:
 
If <math>a_7=1</math>, then we can choose anything for the other 7 variables, so this give us <math>3^7</math>.
 
If <math>a_7=1</math>, then we can choose anything for the other 7 variables, so this give us <math>3^7</math>.
Line 35: Line 35:
 
Note that we have counted all possibilities, because the largest positive positive power of 3 must be greater than or equal to the largest negative positive power of 3, for the number to be nonnegative.
 
Note that we have counted all possibilities, because the largest positive positive power of 3 must be greater than or equal to the largest negative positive power of 3, for the number to be nonnegative.
  
−
== Solution 5 ==
+
==Solution 5==
−
The key is to realize that this question is basically taking place in <math>a\in\{0,1,2\}</math> if each value of <math>a</math> was increased by <math>1</math>, essentially making it into base <math>3</math>. Then the range would be from <math>0\cdot3^7+0\cdot3^6+0\cdot3^5+0\cdot3^4+0\cdot3^3+0\cdot3^2+0\cdot3^1+0\cdot3^0=0</math> to <math>2\cdot3^7+2\cdot3^6+2\cdot3^5+2\cdot3^4+2\cdot3^3+2\cdot3^2+2\cdot3^1+2\cdot3^0=3^8-1=6561-1=6560</math>, yielding <math>6561</math> different values. Since the distribution for all <math>a_i\in \{-1,0,1\}</math> the question originally gave is symmetrical, we retain the <math>3280</math> positive integers and one <math>0</math> but discard the <math>3280</math> negative integers. Thus, we are left with the answer, <math>\boxed{\textbf{(D)} 3281}\qquad</math>.
+
The key is to realize that this question is basically taking place in <math>a\in\{0,1,2\}</math> if each value of <math>a</math> was increased by <math>1</math>, essentially making it into base <math>3</math>. Then the range would be from <math>0\cdot3^7+</math> <math>0\cdot3^6+</math> <math>0\cdot3^5+</math> <math>0\cdot3^4+</math> <math>0\cdot3^3+</math> <math>0\cdot3^2+</math> <math>0\cdot3^1+</math> <math>0\cdot3^0=</math> <math>0</math> to <math>2\cdot3^7+</math> <math>2\cdot3^6+</math> <math>2\cdot3^5+</math> <math>2\cdot3^4+</math> <math>2\cdot3^3+</math> <math>2\cdot3^2+</math> <math>2\cdot3^1+</math> <math>2\cdot3^0=</math> <math>3^8-1=</math> <math>6561-1=</math> <math>6560</math>, yielding <math>6561</math> different values. Since the distribution for all <math>a_i\in \{-1,0,1\}</math> the question originally gave is symmetrical, we retain the <math>3280</math> positive integers and one <math>0</math> but discard the <math>3280</math> negative integers. Thus, we are left with the answer, <math>\boxed{\textbf{(D)} 3281}\qquad</math>. ∎ --anna0kear
 +
 
 +
==Solution 6==
 +
Through trial and error: We start by setting <math>a_i=0</math> for all <math>i≥1</math>. We can see that our range becomes <math>[-1,1]</math> Notice the range, which now has the set of integers <math>-4≤\mathbb{Z}≤4</math>. (is with)
  
 
==See Also==
 
==See Also==

Revision as of 13:36, 10 February 2018

Problem

How many nonnegative integers can be written in the form \[a_7\cdot3^7+a_6\cdot3^6+a_5\cdot3^5+a_4\cdot3^4+a_3\cdot3^3+a_2\cdot3^2+a_1\cdot3^1+a_0\cdot3^0,\] where $a_i\in \{-1,0,1\}$ for $0\le i \le 7$?

$\textbf{(A) } 512 \qquad \textbf{(B) } 729 \qquad \textbf{(C) } 1094 \qquad \textbf{(D) } 3281 \qquad \textbf{(E) } 59,048$

Solution 1

This looks like balanced ternary, in which all the integers with absolute values less than $\frac{3^n}{2}$ are represented in $n$ digits. There are 8 digits. Plugging in 8 into the formula gives a maximum bound of $|x|=3280.5$, which means there are 3280 positive integers, 0, and 3280 negative integers. Since we want all nonnegative integers, there are $3280+1=\boxed{3281}$ integers or $\boxed{D}$.

$QED\blacksquare$

Solution 2

Note that all numbers formed from this sum are either positive, negative or zero. The number of positive numbers formed by this sum is equal to the number of negative numbers formed by this sum, because of symmetry. There is only one way to achieve a sum of zero, if all $a_i=0$. The total number of ways to pick $a_i$ from $i=1, 2, 3, ... 7$ is $3^8=6561$. $\frac{6561-1}{2}=3280$ gives the number of possible negative integers. The question asks for the number of nonnegative integers, so subtracting from the total gives $6561-3280=\boxed{3281}$. (RegularHexagon)

Solution 3

Note that the number of total possibilities (ignoring the conditions set by the problem) is $3^8=6561$. So, E is clearly unrealistic.

Note that if $a_7$ is 1, then it's impossible for \[a_7\cdot3^7+a_6\cdot3^6+a_5\cdot3^5+a_4\cdot3^4+a_3\cdot3^3+a_2\cdot3^2+a_1\cdot3^1+a_0\cdot3^0,\] to be negative. Therefore, if $a_7$ is 1, there are $3^7=2187$ possibilities. (We also must convince ourselves that these $2187$ different sets of coefficients must necessarily yield $2187$ different integer results.)

As A, B, and C are all less than 2187, the answer must be $\boxed{(D) 3281}$

Solution 4

Note that we can do some simple casework: If $a_7=1$, then we can choose anything for the other 7 variables, so this give us $3^7$. If $a_7=0$ and $a_6=1$, then we can choose anything for the other 6 variables, giving us $3^6$. If $a_7=0$, $a_6=0$, and $a_5=1$, then we have $3^5$. Continuing in this vein, we have $3^7+3^6+\cdots+3^1+3^0$ ways to choose the variables' values, except we have to add 1 because we haven't counted the case where all variables are 0. So our total sum is $\boxed{(D) 3281}$. Note that we have counted all possibilities, because the largest positive positive power of 3 must be greater than or equal to the largest negative positive power of 3, for the number to be nonnegative.

Solution 5

The key is to realize that this question is basically taking place in $a\in\{0,1,2\}$ if each value of $a$ was increased by $1$, essentially making it into base $3$. Then the range would be from $0\cdot3^7+$ $0\cdot3^6+$ $0\cdot3^5+$ $0\cdot3^4+$ $0\cdot3^3+$ $0\cdot3^2+$ $0\cdot3^1+$ $0\cdot3^0=$ $0$ to $2\cdot3^7+$ $2\cdot3^6+$ $2\cdot3^5+$ $2\cdot3^4+$ $2\cdot3^3+$ $2\cdot3^2+$ $2\cdot3^1+$ $2\cdot3^0=$ $3^8-1=$ $6561-1=$ $6560$, yielding $6561$ different values. Since the distribution for all $a_i\in \{-1,0,1\}$ the question originally gave is symmetrical, we retain the $3280$ positive integers and one $0$ but discard the $3280$ negative integers. Thus, we are left with the answer, $\boxed{\textbf{(D)} 3281}\qquad$. ∎ --anna0kear

Solution 6

Through trial and error: We start by setting $a_i=0$ for all $i≥1$ (Error compiling LaTeX. Unknown error_msg). We can see that our range becomes $[-1,1]$ Notice the range, which now has the set of integers $-4≤\mathbb{Z}≤4$ (Error compiling LaTeX. Unknown error_msg). (is with)

See Also

2018 AMC 10A (Problems • Answer Key • Resources)
Preceded by
Problem 17 		Followed by
Problem 19
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions
2018 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 12 		Followed by
Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_10A_Problems/Problem_18&oldid=90948"