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

Revision as of 20:31, 24 January 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 $4$ .

-Patrick4President

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

@@ Line 63: / Line 63: @@
 ~bunny1
+== Video Solution 3==
+https://youtu.be/4_x1sgcQCp4?t=112
+~ pi_is_3.14
 ==See Also==

2018 AMC 10B (Problems • Answer Key • Resources)
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

Page

Toolbox

Search