Difference between revisions of "2018 AMC 10B Problems/Problem 16"

(Solution 3)
m (Algebraic Insight into Given Property)
 
(58 intermediate revisions by 26 users not shown)
Line 1: Line 1:
 +
==Problem==
 +
 
Let <math>a_1,a_2,\dots,a_{2018}</math> be a strictly increasing sequence of positive integers such that <cmath>a_1+a_2+\cdots+a_{2018}=2018^{2018}.</cmath>
 
Let <math>a_1,a_2,\dots,a_{2018}</math> be a strictly increasing sequence of positive integers such that <cmath>a_1+a_2+\cdots+a_{2018}=2018^{2018}.</cmath>
 
What is the remainder when <math>a_1^3+a_2^3+\cdots+a_{2018}^3</math> is divided by <math>6</math>?
 
What is the remainder when <math>a_1^3+a_2^3+\cdots+a_{2018}^3</math> is divided by <math>6</math>?
Line 6: Line 8:
 
==Solution 1==
 
==Solution 1==
  
<math>n^{3}\equiv n \pmod{6}</math>
+
One could simply list out all the residues to the third power <math>\mod 6</math>. (Edit: Euler's totient theorem is not a valid approach to showing that they are all congruent <math>\mod 6</math>. This is due to the fact that <math>a_k</math> need not be relatively prime to <math>6</math>.)
 +
 
 +
Therefore the answer is congruent to <math>2018^{2018}\equiv 2^{2018} \pmod{6} = \boxed{ (E)4}</math>
  
Therefore the answer is congruent to <math>2018^{2018}\equiv 2^{2018} \pmod{6} = \boxed{ (E)4}</math> Please don't take credit, thanks!
+
Note from Williamgolly: We can WLOG assume <math>a_1,a_2... a_{2017} \equiv 0 \pmod 6</math> and have <math>a_{2018} \equiv 2 \pmod 6</math> to make life easier.
  
 
==Solution 2==
 
==Solution 2==
(not very good one)
 
  
Note that <math>\left(a_1+a_2+\cdots+a_{2018}\right)^3=a_1^3+a_2^3+\cdots+a_{2018}^3+3a_1^2\left(a_1+a_2+\cdots+a_{2018}-a_1\right)+3a_2^2\left(a_1+a_2+\cdots+a_{2018}-a_2\right)+\cdots+3a_{2018}^2\left(a_1+a_2+\cdots+a_{2018}-a_{2018}\right)+6\prod_{i\neq j\neq k}^{2018} a_ia_ja_k</math>
+
Note that <math>\left(a_1+a_2+\cdots+a_{2018}\right)^3=a_1^3+a_2^3+\cdots+a_{2018}^3+3a_1^2\left(a_1+a_2+\cdots+a_{2018}-a_1\right)+3a_2^2\left(a_1+a_2+\cdots+a_{2018}-a_2\right)+\cdots+3a_{2018}^2\left(a_1+a_2+\cdots+a_{2018}-a_{2018}\right)+6\sum_{i\neq j\neq k}^{2018} a_ia_ja_k</math>
  
 
Note that <math>
 
Note that <math>
a_1^3+a_2^3+\cdots+a_{2018}^3+3a_1^2\left(a_1+a_2+\cdots+a_{2018}-a_1\right)+3a_2^2\left(a_1+a_2+\cdots+a_{2018}-a_2\right)+\cdots+3a_{2018}^2\left(a_1+a_2+\cdots+a_{2018}-a_{2018}\right)+6\prod_{i\neq j\neq k}^{2018} a_ia_ja_k\equiv a_1^3+a_2^3+\cdots+a_{2018}^3+3a_1^2(2018-a_1)+3a_2^2(2018-a_2)+\cdots+3a_{2018}^2(2018-a_{2018})
+
a_1^3+a_2^3+\cdots+a_{2018}^3+3a_1^2\left(a_1+a_2+\cdots+a_{2018}-a_1\right)+3a_2^2\left(a_1+a_2+\cdots+a_{2018}-a_2\right)+\cdots+3a_{2018}^2\left(a_1+a_2+\cdots+a_{2018}-a_{2018}\right)+6\sum_{i\neq j\neq k}^{2018} a_ia_ja_k\equiv a_1^3+a_2^3+\cdots+a_{2018}^3+3a_1^2({2018}^{2018}-a_1)+3a_2^2({2018}^{2018}-a_2)+\cdots+3a_{2018}^2({2018}^{2018}-a_{2018})
 
\equiv -2(a_1^3+a_2^3+\cdots+a_{2018}^3)\pmod 6
 
\equiv -2(a_1^3+a_2^3+\cdots+a_{2018}^3)\pmod 6
 
</math>
 
</math>
Line 23: Line 26:
 
Thus, <math>a_1^3+a_2^3+\cdots+a_{2018}^3\equiv 1\pmod 3</math>. However, since cubing preserves parity, and the sum of the individual terms is even, the some of the cubes is also even, and our answer is <math>\boxed{\text{(E) }4}</math>
 
Thus, <math>a_1^3+a_2^3+\cdots+a_{2018}^3\equiv 1\pmod 3</math>. However, since cubing preserves parity, and the sum of the individual terms is even, the some of the cubes is also even, and our answer is <math>\boxed{\text{(E) }4}</math>
  
==Solution 3==
+
==Solution 3 (Partial Proof)==
 +
First, we can assume that the problem will have a consistent answer for all possible values of <math>a_1</math>. For the purpose of this solution, we will assume that <math>a_1 = 1</math>.
  
We first note that <math>1^3+2^3+...=(1+2+...)^2</math>. So what we are trying to find is what <math>\left(2018^{2018}\right)^3=</math>\left(2018)^{4036}\right<math> is mod </math>6<math>. We start by noting that </math>2018<math> is congruent to </math>2<math> mod </math>6<math>. So we are trying to find </math>2^4036<math> mod </math>6<math>. Instead of trying to do this with some number theory skills, we could just look for a pattern. We start small powers of </math>2<math> and see that </math>2^1<math> is </math>2<math> mod </math>6<math>, </math>2^2<math> is </math>4<math> mod </math>6<math>, </math>2^3<math> is </math>2<math> mod </math>6<math>, </math>2^4<math> is </math>4<math> mod </math>6<math>, and so on... So we see that since </math>2^(4036)<math> has an even power, it must be congruent to </math>4<math> mod </math>6<math>, thus giving our answer </math>\boxed{\text{(E) }4}$. You can prove this pattern using mods. But I thought this was easier.
+
We first note that <math>1^3+2^3+...+n^3 = (1+2+...+n)^2</math>. So what we are trying to find is what <math>\left(2018^{2018}\right)^2=\left(2018^{4036}\right)</math> mod <math>6</math>. We start by noting that <math>2018</math> is congruent to <math>2 \pmod{6}</math>. So we are trying to find <math>\left(2^{4036}\right) \pmod{6}</math>. Instead of trying to do this with some number theory skills, we could just look for a pattern. We start with small powers of <math>2</math> and see that <math>2^1</math> is <math>2</math> mod <math>6</math>, <math>2^2</math> is <math>4</math> mod <math>6</math>, <math>2^3</math> is <math>2</math> mod <math>6</math>, <math>2^4</math> is <math>4</math> mod <math>6</math>, and so on... So we see that since <math>\left(2^{4036}\right)</math> has an even power, it must be congruent to <math>4 \pmod{6}</math>, thus giving our answer <math>\boxed{\text{(E) }4}</math>. You can prove this pattern using mods. But I thought this was easier.
  
 
-TheMagician
 
-TheMagician
 +
 +
==Solution 4 (Lazy solution)==
 +
First, we can assume that the problem will have a consistent answer for all possible values of <math>a_1</math>. For the purpose of this solution, assume <math>a_1, a_2, ... a_{2017}</math> are multiples of 6 and find <math>2018^{2018} \pmod{6}</math> (which happens to be <math>4</math>). Then <math>{a_1}^3 + ... + {a_{2018}}^3</math> is congruent to <math>64 \pmod{6}</math> or just <math>\boxed{\textbf{(E)}  4}</math>.
 +
 +
-Patrick4President
 +
 +
~minor edit made by CatachuKetchup~
 +
 +
==Solution 5 (Nichomauss' Theorem)==
 +
 +
Seeing the cubes of numbers, we think of Nichomauss's theorem, which states that <math>(a_1^3 + a_2^3 + ... + a_n^3) = (a_1 + a_2 + ... + a_n)^2</math>. We can do this and deduce that <math>(a_1^3 + a_2^3 + ... + a_{2018}^3) = 2018^{2018}</math> squared.
 +
 +
Now, we find <math>2018\mod 6</math>, which is 2. This means that we need to find <math>2^{2018} \mod {6}</math>, which we can find using a pattern to be <math>4</math>. Therefore, the answer is <math>4^2\mod 6</math>, which is congruent to <math>\boxed{\textbf{(E)} 4}</math>
 +
 +
-ericshi1685
 +
<br>
 +
Minor edits by fasterthanlight
 +
 +
==Algebraic Insight into Given Property==
 +
Mods is a good way to prove <math>a^3 \equiv a \pmod6</math>: residues are simply <math>3, \pm 2, \pm 1, 0</math>. Only <math>2</math> and <math>3</math> are necessary to check.
 +
Another way is to observe that <math>a^3-a</math> factors into <math>(a-1)a(a+1)</math>. Any <math>k</math> consecutive numbers must be a multiple of <math>k</math>, so <math>a^3-a</math> is both divisible by <math>2</math> and <math>3</math>. This provides an algebraic method for proving <math>a^3 \equiv a \pmod6</math> for all <math>a</math>.
 +
 +
==Video Solution 1==
 +
With Modular Arithmetic Intro
 +
https://www.youtube.com/watch?v=wbv3TArroSs
 +
 +
~IceMatrix
 +
 +
==Video Solution 2==
 +
https://www.youtube.com/watch?v=SRjZ6B5DR74
 +
 +
~bunny1
 +
 +
== Video Solution 3==
 +
https://youtu.be/4_x1sgcQCp4?t=112
 +
 +
~ pi_is_3.14
  
 
==See Also==
 
==See Also==

Latest revision as of 18:05, 4 July 2021

Problem

Let $a_1,a_2,\dots,a_{2018}$ be a strictly increasing sequence of positive integers such that \[a_1+a_2+\cdots+a_{2018}=2018^{2018}.\] What is the remainder when $a_1^3+a_2^3+\cdots+a_{2018}^3$ is divided by $6$?

$\textbf{(A)}\ 0\qquad\textbf{(B)}\ 1\qquad\textbf{(C)}\ 2\qquad\textbf{(D)}\ 3\qquad\textbf{(E)}\ 4$

Solution 1

One could simply list out all the residues to the third power $\mod 6$. (Edit: Euler's totient theorem is not a valid approach to showing that they are all congruent $\mod 6$. This is due to the fact that $a_k$ need not be relatively prime to $6$.)

Therefore the answer is congruent to $2018^{2018}\equiv 2^{2018} \pmod{6} = \boxed{ (E)4}$

Note from Williamgolly: We can WLOG assume $a_1,a_2... a_{2017} \equiv 0 \pmod 6$ and have $a_{2018} \equiv 2 \pmod 6$ to make life easier.

Solution 2

Note that $\left(a_1+a_2+\cdots+a_{2018}\right)^3=a_1^3+a_2^3+\cdots+a_{2018}^3+3a_1^2\left(a_1+a_2+\cdots+a_{2018}-a_1\right)+3a_2^2\left(a_1+a_2+\cdots+a_{2018}-a_2\right)+\cdots+3a_{2018}^2\left(a_1+a_2+\cdots+a_{2018}-a_{2018}\right)+6\sum_{i\neq j\neq k}^{2018} a_ia_ja_k$

Note that $a_1^3+a_2^3+\cdots+a_{2018}^3+3a_1^2\left(a_1+a_2+\cdots+a_{2018}-a_1\right)+3a_2^2\left(a_1+a_2+\cdots+a_{2018}-a_2\right)+\cdots+3a_{2018}^2\left(a_1+a_2+\cdots+a_{2018}-a_{2018}\right)+6\sum_{i\neq j\neq k}^{2018} a_ia_ja_k\equiv a_1^3+a_2^3+\cdots+a_{2018}^3+3a_1^2({2018}^{2018}-a_1)+3a_2^2({2018}^{2018}-a_2)+\cdots+3a_{2018}^2({2018}^{2018}-a_{2018}) \equiv -2(a_1^3+a_2^3+\cdots+a_{2018}^3)\pmod 6$ Therefore, $-2(a_1^3+a_2^3+\cdots+a_{2018}^3)\equiv \left(2018^{2018}\right)^3\equiv\left( 2^{2018}\right)^3\equiv 4^3\equiv 4\pmod{6}$.

Thus, $a_1^3+a_2^3+\cdots+a_{2018}^3\equiv 1\pmod 3$. However, since cubing preserves parity, and the sum of the individual terms is even, the some of the cubes is also even, and our answer is $\boxed{\text{(E) }4}$

Solution 3 (Partial Proof)

First, we can assume that the problem will have a consistent answer for all possible values of $a_1$. For the purpose of this solution, we will assume that $a_1 = 1$.

We first note that $1^3+2^3+...+n^3 = (1+2+...+n)^2$. So what we are trying to find is what $\left(2018^{2018}\right)^2=\left(2018^{4036}\right)$ mod $6$. We start by noting that $2018$ is congruent to $2 \pmod{6}$. So we are trying to find $\left(2^{4036}\right) \pmod{6}$. Instead of trying to do this with some number theory skills, we could just look for a pattern. We start with small powers of $2$ and see that $2^1$ is $2$ mod $6$, $2^2$ is $4$ mod $6$, $2^3$ is $2$ mod $6$, $2^4$ is $4$ mod $6$, and so on... So we see that since $\left(2^{4036}\right)$ has an even power, it must be congruent to $4 \pmod{6}$, thus giving our answer $\boxed{\text{(E) }4}$. You can prove this pattern using mods. But I thought this was easier.

-TheMagician

Solution 4 (Lazy solution)

First, we can assume that the problem will have a consistent answer for all possible values of $a_1$. For the purpose of this solution, assume $a_1, a_2, ... a_{2017}$ are multiples of 6 and find $2018^{2018} \pmod{6}$ (which happens to be $4$). Then ${a_1}^3 + ... + {a_{2018}}^3$ is congruent to $64 \pmod{6}$ or just $\boxed{\textbf{(E)}  4}$.

-Patrick4President

~minor edit made by CatachuKetchup~

Solution 5 (Nichomauss' Theorem)

Seeing the cubes of numbers, we think of Nichomauss's theorem, which states that $(a_1^3 + a_2^3 + ... + a_n^3) = (a_1 + a_2 + ... + a_n)^2$. We can do this and deduce that $(a_1^3 + a_2^3 + ... + a_{2018}^3) = 2018^{2018}$ squared.

Now, we find $2018\mod 6$, which is 2. This means that we need to find $2^{2018} \mod {6}$, which we can find using a pattern to be $4$. Therefore, the answer is $4^2\mod 6$, which is congruent to $\boxed{\textbf{(E)} 4}$

-ericshi1685
Minor edits by fasterthanlight

Algebraic Insight into Given Property

Mods is a good way to prove $a^3 \equiv a \pmod6$: residues are simply $3, \pm 2, \pm 1, 0$. Only $2$ and $3$ are necessary to check. Another way is to observe that $a^3-a$ factors into $(a-1)a(a+1)$. Any $k$ consecutive numbers must be a multiple of $k$, so $a^3-a$ is both divisible by $2$ and $3$. This provides an algebraic method for proving $a^3 \equiv a \pmod6$ for all $a$.

Video Solution 1

With Modular Arithmetic Intro https://www.youtube.com/watch?v=wbv3TArroSs

~IceMatrix

Video Solution 2

https://www.youtube.com/watch?v=SRjZ6B5DR74

~bunny1

Video Solution 3

https://youtu.be/4_x1sgcQCp4?t=112

~ pi_is_3.14

See Also

2018 AMC 10B (ProblemsAnswer KeyResources)
Preceded by
Problem 15
Followed by
Problem 17
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

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

Invalid username
Login to AoPS