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 10B Problems/Problem 16"
Line 27: Line 27:
  
 
==Solution 3 (Partial Proof)==
 
==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 problem, we will assume that <math>a_1 = 1</math>
+
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+...+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.
 
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.
Line 34: Line 34:
  
 
==Solution 4 (Lazy solution)==
 
==Solution 4 (Lazy 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>4</math>.  
+
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>4</math>.  
  
 
-Patrick4President
 
-Patrick4President

Revision as of 15:30, 27 January 2020

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=0(mod6)$ and have $a_2018=2(mod6)$ 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 (Fermat's Little Theorem)

First note that each $a_{i}^3 \equiv a_{i} \pmod 3$ by Fermat's Little Theorem. This implies that $a_{1}^3+...+a_{2018}^3 \equiv a_{1}+...+a_{2018} \equiv 2^{2018} \equiv 1 \pmod{3}$. Also, all $a_{i}^2 \equiv a_{i} \pmod{2}$, hence $a_{i}^3 \equiv (a_{i})(a_{i}^2) \equiv a_{i}^2 \equiv a_{i} \pmod{2}$ by Fermat's Little Theorem.Thus, $a_{1}^3+...a_{2018}^3 \equiv 2^{2018} \equiv 0 \pmod{2}$. Now set $x=a_{1}^3+...+a_{2018}^3$. Then, we have the congruences $x \equiv 0 \pmod{2}$ and $x \equiv 1 \pmod{3}$. By the Chinese Remainder Theorem, a solution must exist, and indeed solving the congruence we get that $x \equiv 4 \pmod{6}$. Thus, the answer is $\boxed{ (E)4}$

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

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_10B_Problems/Problem_16&oldid=115684"