Difference between revisions of "2018 AMC 10B Problems/Problem 16"
TheMagician (talk | contribs) (→Solution 2) |
(→Solution 4 (Lazy solution)) |
||
(61 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> | + | 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> |
− | + | 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. | |
− | |||
− | 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\ | + | ==Solution 2== |
+ | |||
+ | 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\ | + | 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 | + | ==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>( | + | 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 22:09, 30 January 2021
Contents
Problem
Let be a strictly increasing sequence of positive integers such that What is the remainder when is divided by ?
Solution 1
One could simply list out all the residues to the third power . (Edit: Euler's totient theorem is not a valid approach to showing that they are all congruent . This is due to the fact that need not be relatively prime to .)
Therefore the answer is congruent to
Note from Williamgolly: We can WLOG assume and have to make life easier.
Solution 2
Note that
Note that Therefore, .
Thus, . 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
Solution 3 (Partial Proof)
First, we can assume that the problem will have a consistent answer for all possible values of . For the purpose of this solution, we will assume that .
We first note that . So what we are trying to find is what mod . We start by noting that is congruent to . So we are trying to find . Instead of trying to do this with some number theory skills, we could just look for a pattern. We start with small powers of and see that is mod , is mod , is mod , is mod , and so on... So we see that since has an even power, it must be congruent to , thus giving our answer . 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 . For the purpose of this solution, assume are multiples of 6 and find (which happens to be ). Then is congruent to or just .
-Patrick4President
~minor edit made by CatachuKetchup~
Solution 5 (Nichomauss' Theorem)
Seeing the cubes of numbers, we think of Nichomauss's theorem, which states that . We can do this and deduce that squared.
Now, we find , which is 2. This means that we need to find , which we can find using a pattern to be . Therefore, the answer is , which is congruent to
-ericshi1685
Minor edits by fasterthanlight
Algebraic Insight into Given Property
Mods is a good way to prove : residues are simply . Only and are necessary to check. Another way is to observe that factors into . Any consecutive numbers must be a multiple of , so is both divisible by and . This provides an algebraic method for proving for all .
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 (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.