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"

(→‎Solution 9)
(→‎Solution 3)
 
(10 intermediate revisions by 6 users not shown)
Line 1: Line 1:
−
{{duplicate|[[2018 AMC 12A Problems|2018 AMC 12A #13]] and [[2018 AMC 10A Problems|2018 AMC 10A #18]]}}
+
{{duplicate|[[2018 AMC 10A Problems/Problem 18|2018 AMC 10A #18]] and [[2018 AMC 12A Problems/Problem 13|2018 AMC 12A #13]]}}
  
 
==Problem==
 
==Problem==
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=0, 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 non-negative integers, so subtracting from the total gives <math>6561-3280=\boxed{\textbf{(D) } 3281}</math>. (RegularHexagon, KLBBC minor changes)
 
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=0, 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 non-negative integers, so subtracting from the total gives <math>6561-3280=\boxed{\textbf{(D) } 3281}</math>. (RegularHexagon, KLBBC minor changes)
  
−
==Solution 3==
+
==Solution 3 (Answer choices)==
 
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 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.
  
−
==Casework and Recursion Solution 5==
+
==Solution 5 (Casework and Recursion)==
 
This solution has a similar idea to that of above.
 
This solution has a similar idea to that of above.
 
We will start off with casework on <math>a_{7}</math>:
 
We will start off with casework on <math>a_{7}</math>:
 
If <math>a_7 = -1</math>, we can show that there is no way to assign the values of <math>-1, 0, 1</math> to the other <math>a_{i}</math>'s for <math>0 \leq i \leq 6</math>. This is because even if we make all of the other <math>a_{i}</math> equal to <math>1</math>, we will have that our number is <math>(-1)(3^{7}) + (3^{6}+3^{5}+...+3^{0}) = -3^{7} + \frac{3^{7}-1}{3-1}</math>. However, note that since <math>\frac{3^{7}-1}{3-1} < 3^{7}</math>, <math>-3^{7} + \frac{3^{7}-1}{3-1} < 0</math>.
 
If <math>a_7 = -1</math>, we can show that there is no way to assign the values of <math>-1, 0, 1</math> to the other <math>a_{i}</math>'s for <math>0 \leq i \leq 6</math>. This is because even if we make all of the other <math>a_{i}</math> equal to <math>1</math>, we will have that our number is <math>(-1)(3^{7}) + (3^{6}+3^{5}+...+3^{0}) = -3^{7} + \frac{3^{7}-1}{3-1}</math>. However, note that since <math>\frac{3^{7}-1}{3-1} < 3^{7}</math>, <math>-3^{7} + \frac{3^{7}-1}{3-1} < 0</math>.
 
If <math>a_{7}=0</math>, we can ignore <math>a_{7}</math> and pretend like it never even existed. This then simplifies the problem: the question remains the same, except that instead of having <math>a_{0}...a_{7}</math>, we only have <math>a_{0}...a_{6}</math>. Now, we introduce some notation: let the number of nonnegative integers that can be written in the form of <math>a_{n} \cdot 3^{n} + ... + a_{0} \cdot 3^{0}</math> be denoted as <math>S_{n}</math>. Then, the problem is asking us for <math>S_{7}</math>, and the total number of nonnegative integers we get from this case is <math>S_{6}</math>. Let's keep this in mind and revisit this idea later.
 
If <math>a_{7}=0</math>, we can ignore <math>a_{7}</math> and pretend like it never even existed. This then simplifies the problem: the question remains the same, except that instead of having <math>a_{0}...a_{7}</math>, we only have <math>a_{0}...a_{6}</math>. Now, we introduce some notation: let the number of nonnegative integers that can be written in the form of <math>a_{n} \cdot 3^{n} + ... + a_{0} \cdot 3^{0}</math> be denoted as <math>S_{n}</math>. Then, the problem is asking us for <math>S_{7}</math>, and the total number of nonnegative integers we get from this case is <math>S_{6}</math>. Let's keep this in mind and revisit this idea later.
−
If <math>a_{7}=1</math>, we can show that no matter what values we assign to the rest of the <math>a_{i}</math>, we will always get a nonnegative integer (we can make this even stricter and say positive integer). This is because of something we figured out in the first case: <math>\frac{3^{7}-1}{3-1} < 3^{7}</math>. So, even if we let <math>a_{i}=1</math> for <math>0 \leq i \leq 6</math>, we will still have <math>3^{7} - (3^{6}+...+3^{0}) > 0</math>. So, for this case, we have <math>3^7</math> possible nonnegative integers.
+
If <math>a_{7}=1</math>, we can show that no matter what values we assign to the rest of the <math>a_{i}</math>, we will always get a nonnegative integer (we can make this even stricter and say positive integer). This is because of something we figured out in the first case: <math>\frac{3^{7}-1}{3-1} < 3^{7}</math>. So, even if we let <math>a_{i}=-1</math> for <math>0 \leq i \leq 6</math>, we will still have <math>3^{7} - (3^{6}+...+3^{0}) > 0</math>. So, for this case, we have <math>3^7</math> possible nonnegative integers.
 
Totalling up our values from the three cases, we see that <math>S_{7} = 0 + S_{6} + 3^{7}</math>. In fact, using the reasoning from the three cases above, we can deduce that, for all positive integers <math>n</math>, <math>S_{n} = 3^{n} + S_{n-1}</math>. We can now start building up our values for <math>S</math>: <math>S_{0} = 2</math> (<math>a_{0} = 0, 1</math>), <math>S_{1} = 3^{1}+S_{0} = 5, S_{2} = 14, ..., S_{6}=1094</math>. So, we have <math>S_{7} = 2187 + 1094 = \boxed{3281}</math>, which is answer choice <math>\boxed{\text{D}}</math>.
 
Totalling up our values from the three cases, we see that <math>S_{7} = 0 + S_{6} + 3^{7}</math>. In fact, using the reasoning from the three cases above, we can deduce that, for all positive integers <math>n</math>, <math>S_{n} = 3^{n} + S_{n-1}</math>. We can now start building up our values for <math>S</math>: <math>S_{0} = 2</math> (<math>a_{0} = 0, 1</math>), <math>S_{1} = 3^{1}+S_{0} = 5, S_{2} = 14, ..., S_{6}=1094</math>. So, we have <math>S_{7} = 2187 + 1094 = \boxed{3281}</math>, which is answer choice <math>\boxed{\text{D}}</math>.
 
~advanture
 
~advanture
Line 61: Line 61:
  
 
==Solution 9==
 
==Solution 9==
−
Notice that there are <math>3^8</math> options for <math>a_7, a_6, \cdots a_0</math> since each <math>a_i</math> can take the value of <math>-1</math> or <math>0</math> or <math>1</math>. Now we want to find how many of them are positive and then we can add one in the end to account for <math>0</math>(they are asking for non-negative).  
+
Notice that there are <math>3^8</math> options for <math>a_7, a_6, \cdots a_0</math> since each <math>a_i</math> can take on the value <math>-1</math>, <math>0</math>, or <math>1</math>. Now we want to find how many of them are positive and then we can add one in the end to account for <math>0</math> (they are asking for non-negative).  
  
 
By symmetry (look out for these on the contest), we see that exactly half of them are positive. So <math>\lfloor{\tfrac{3^8}{2}}\rfloor = 3280.</math> Now we will add <math>1</math> because of the <math>0</math> to account for the non-negative solutions.  
 
By symmetry (look out for these on the contest), we see that exactly half of them are positive. So <math>\lfloor{\tfrac{3^8}{2}}\rfloor = 3280.</math> Now we will add <math>1</math> because of the <math>0</math> to account for the non-negative solutions.  
Line 67: Line 67:
 
So our final answer is <math>3280 + 1 = 3281</math> which is <math>\boxed{\textbf{(D) } 3281}</math>.
 
So our final answer is <math>3280 + 1 = 3281</math> which is <math>\boxed{\textbf{(D) } 3281}</math>.
  
−
==Video Solution==
+
==Solution 10==
 +
Obviously, there are <math>3^8 = 6561</math> possible, and one of them is 0, so other <math>6560</math> are either positive or negative. By the symmetry, we can get the answer is <math>6560/2 + 1</math> which is <math>\boxed{\textbf{(D) } 3281}</math>.
 +
 
 +
~ Little
 +
 
 +
==Solution 11 (2 seconds)==
 +
The solution has to obviously be smaller than <math>3^{7-0+1}=3^8</math> but larger than <math>3^{(7-0+1)-1} = 3^7.</math> The only remaining answer is <math>\boxed{\textbf{(D) } 3281}.</math>
 +
~mathboy282
 +
 
 +
==Video Solution by Pi Academy (FAST and easy)==
 +
 
 +
https://youtu.be/cTb6AMpit5o?si=dKGnTcQlNHGLLJlD
 +
 
 +
~ Pi Academy
 +
 
 +
== Video Solution ==
 
https://youtu.be/0xmbHDcUI2w
 
https://youtu.be/0xmbHDcUI2w
  
 
~IceMatrix
 
~IceMatrix
−
 
−
==Difficulty==
 
−
Out of a scale of 10, we rate this as 7 due to its complexity, however the solution is both traditional and easy.
 
−
~ Justin6688 and friend me
 
  
 
==See Also==
 
==See Also==

Latest revision as of 02:02, 31 October 2024

The following problem is from both the 2018 AMC 10A #18 and 2018 AMC 12A #13, so both problems redirect to this page.

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 for the balanced ternary 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{\textbf{D}}$.

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=0, 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 non-negative integers, so subtracting from the total gives $6561-3280=\boxed{\textbf{(D) } 3281}$. (RegularHexagon, KLBBC minor changes)

Solution 3 (Answer choices)

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{\textbf{(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{\textbf{(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 (Casework and Recursion)

This solution has a similar idea to that of above. We will start off with casework on $a_{7}$: If $a_7 = -1$, we can show that there is no way to assign the values of $-1, 0, 1$ to the other $a_{i}$'s for $0 \leq i \leq 6$. This is because even if we make all of the other $a_{i}$ equal to $1$, we will have that our number is $(-1)(3^{7}) + (3^{6}+3^{5}+...+3^{0}) = -3^{7} + \frac{3^{7}-1}{3-1}$. However, note that since $\frac{3^{7}-1}{3-1} < 3^{7}$, $-3^{7} + \frac{3^{7}-1}{3-1} < 0$. If $a_{7}=0$, we can ignore $a_{7}$ and pretend like it never even existed. This then simplifies the problem: the question remains the same, except that instead of having $a_{0}...a_{7}$, we only have $a_{0}...a_{6}$. Now, we introduce some notation: let the number of nonnegative integers that can be written in the form of $a_{n} \cdot 3^{n} + ... + a_{0} \cdot 3^{0}$ be denoted as $S_{n}$. Then, the problem is asking us for $S_{7}$, and the total number of nonnegative integers we get from this case is $S_{6}$. Let's keep this in mind and revisit this idea later. If $a_{7}=1$, we can show that no matter what values we assign to the rest of the $a_{i}$, we will always get a nonnegative integer (we can make this even stricter and say positive integer). This is because of something we figured out in the first case: $\frac{3^{7}-1}{3-1} < 3^{7}$. So, even if we let $a_{i}=-1$ for $0 \leq i \leq 6$, we will still have $3^{7} - (3^{6}+...+3^{0}) > 0$. So, for this case, we have $3^7$ possible nonnegative integers. Totalling up our values from the three cases, we see that $S_{7} = 0 + S_{6} + 3^{7}$. In fact, using the reasoning from the three cases above, we can deduce that, for all positive integers $n$, $S_{n} = 3^{n} + S_{n-1}$. We can now start building up our values for $S$: $S_{0} = 2$ ($a_{0} = 0, 1$), $S_{1} = 3^{1}+S_{0} = 5, S_{2} = 14, ..., S_{6}=1094$. So, we have $S_{7} = 2187 + 1094 = \boxed{3281}$, which is answer choice $\boxed{\text{D}}$. ~advanture

Solution 6

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 7

First, set $a_i=0$ for all $i\geq1$. The range would be the integers for which $[-1,1]$. If $a_i=0$ for all $i\geq2$, our set expands to include all integers such that $-4\leq\mathbb{Z}\leq4$. Similarly, when $i\geq3$ we get $-13\leq\mathbb{Z}\leq13$, and when $i\geq4$ the range is $-40\leq\mathbb{Z}\leq40$. The pattern continues until we reach $i=7$, where $-3280\leq\mathbb{Z}\leq3280$. Because we are only looking for positive integers, we filter out all $\mathbb{Z}<0$, leaving us with all integers between $0\leq\mathbb{Z}\leq3280$, inclusive. The answer becomes $\boxed{\textbf{(D) } 3281}$. --anna0kear

Solution 8

To get the number of integers, we can get the highest positive integer that can be represented using \[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$.

Note that the least nonnegative integer that can be represented is $0$, when all $a_i=0$. The highest number will be the number when all $a_i=1$. That will be \[3^7+3^6+3^5+3^4+3^3+3^2+3^1+3^0=\frac{3^8-1}{3-1}\] \[=3280\]

Therefore, there are $3280$ positive integers and $(3280+1)$ nonnegative integers (while including $0$) that can be represented. Our answer is $\boxed{\textbf{(D) } 3281}$

~OlutosinNGA

Solution 9

Notice that there are $3^8$ options for $a_7, a_6, \cdots a_0$ since each $a_i$ can take on the value $-1$, $0$, or $1$. Now we want to find how many of them are positive and then we can add one in the end to account for $0$ (they are asking for non-negative).

By symmetry (look out for these on the contest), we see that exactly half of them are positive. So $\lfloor{\tfrac{3^8}{2}}\rfloor = 3280.$ Now we will add $1$ because of the $0$ to account for the non-negative solutions.

So our final answer is $3280 + 1 = 3281$ which is $\boxed{\textbf{(D) } 3281}$.

Solution 10

Obviously, there are $3^8 = 6561$ possible, and one of them is 0, so other $6560$ are either positive or negative. By the symmetry, we can get the answer is $6560/2 + 1$ which is $\boxed{\textbf{(D) } 3281}$.

~ Little

Solution 11 (2 seconds)

The solution has to obviously be smaller than $3^{7-0+1}=3^8$ but larger than $3^{(7-0+1)-1} = 3^7.$ The only remaining answer is $\boxed{\textbf{(D) } 3281}.$ ~mathboy282

Video Solution by Pi Academy (FAST and easy)

https://youtu.be/cTb6AMpit5o?si=dKGnTcQlNHGLLJlD

~ Pi Academy

Video Solution

https://youtu.be/0xmbHDcUI2w

~IceMatrix

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=231055"