Difference between revisions of "2020 AIME II Problems/Problem 10"
(→Problem) |
Marcopolo96 (talk | contribs) m (→Solution 2 (using the sum of cubes formula)) |
||
(34 intermediate revisions by 11 users not shown) | |||
Line 1: | Line 1: | ||
− | = Problem = | + | == Problem == |
Find the sum of all positive integers <math>n</math> such that when <math>1^3+2^3+3^3+\cdots +n^3</math> is divided by <math>n+5</math>, the remainder is <math>17</math>. | Find the sum of all positive integers <math>n</math> such that when <math>1^3+2^3+3^3+\cdots +n^3</math> is divided by <math>n+5</math>, the remainder is <math>17</math>. | ||
− | == Solution 1 == | + | == Solution 1 (If you don't remember the formula for sum of cubes) == |
We first note that since the remainder is <math>17</math> and we are dividing by <math>n+5</math>, <math>n+5</math> must be greater than <math>17</math>, meaning that <math>n</math> has to be at least <math>13</math>. | We first note that since the remainder is <math>17</math> and we are dividing by <math>n+5</math>, <math>n+5</math> must be greater than <math>17</math>, meaning that <math>n</math> has to be at least <math>13</math>. | ||
− | We then notice that we can pair the <math>5^3</math> term with the <math>n^3</math> term to factor it into <math>(n+5)(n^2-5n+25)</math> using the sum of cubes | + | We then notice that we can pair the <math>5^3</math> term with the <math>n^3</math> term to factor it into <math>(n+5)(n^2-5n+25)</math> using the sum of two cubes factorization (<math>a^3+b^3=(a+b)(a^2-ab+b^2)</math>), which is divisible by <math>n+5</math>. We can do the same for the <math>6^3</math> term with the <math>(n-1)^3</math> term, the <math>7^3</math> term with the <math>(n-2)^3</math>, and so on, which are all divisible by <math>n+5</math>. However, when <math>n</math> is odd, we will have a middle term that is not paired with any other terms, which is not necessarily divisible by <math>n+5</math>. Thus, we have two cases: |
<br><br> | <br><br> | ||
<math>\textbf{CASE 1: } n</math> is even <br> | <math>\textbf{CASE 1: } n</math> is even <br> | ||
Line 18: | Line 18: | ||
If <math>n+5=83</math>, we have that <math>n=78</math>, which is <math>\geq 13</math>, so one of our solutions is <math>n=78</math>, and we are done with our first case. | If <math>n+5=83</math>, we have that <math>n=78</math>, which is <math>\geq 13</math>, so one of our solutions is <math>n=78</math>, and we are done with our first case. | ||
<br><br> | <br><br> | ||
− | <math>\textbf{CASE 2: } n</math> is odd | + | <math>\textbf{CASE 2: } n</math> is odd <br> |
− | If <math>n</math> is odd, the only term that does not pair is the arithmetic mean of the numbers under the cube of the largest and smallest terms that would pair, or <math>(\frac{n+5}{2})^3</math>. Therefore, as all other terms that are <math>\geq 5^3</math> pair, the requirement that we have is | + | If <math>n</math> is odd, the only term that does not pair is the arithmetic mean of the numbers under the cube of the largest and smallest terms that would pair, or <math>\left(\frac{n+5}{2}\right)^3</math>. Therefore, as all other terms that are <math>\geq 5^3</math> pair, the requirement that we have is |
<cmath>1^3+2^3+3^3+4^3+\left(\frac{n+5}{2}\right)^3\equiv 17\pmod {n+5}.</cmath> | <cmath>1^3+2^3+3^3+4^3+\left(\frac{n+5}{2}\right)^3\equiv 17\pmod {n+5}.</cmath> | ||
Calculating and simplifying, we have that | Calculating and simplifying, we have that | ||
Line 48: | Line 48: | ||
<br><br> | <br><br> | ||
~ CoolCarsOnTheRun | ~ CoolCarsOnTheRun | ||
+ | |||
+ | ==Solution 2 (using the sum of cubes formula)== | ||
+ | The formula for the sum of cubes is as follows: | ||
+ | <cmath>1^3+2^3+3^3+...+n^3=(1+2+3+...+n)^2=\left(\frac{n(n+1)}{2}\right)^2</cmath> | ||
+ | So let's apply this to this problem. | ||
+ | |||
+ | Let <math>m=n+5</math>. Then we have | ||
+ | <cmath>1^3+2^3+3^3+\cdots+(m-5)^3\equiv 17 \mod m</cmath> | ||
+ | <cmath>\left(\frac{(m-5)(m-4)}{2}\right)^2\equiv 17 \mod m </cmath> | ||
+ | <cmath>\frac{400}{4}\equiv 17 \mod m </cmath> | ||
+ | <cmath>332 \equiv 0 \mod m </cmath> | ||
+ | So, <math>m\in\{83,166,332\}</math>. Testing the cases, only <math>332</math> fails. This leaves <math>78+161=\boxed{239}</math>. | ||
+ | |||
+ | ==Solution 3 (Official MAA 1)== | ||
+ | The sum of the cubes from 1 to <math>n</math> is | ||
+ | <cmath>1^3+2^3+\cdots+n^3=\frac{n^2(n+1)^2}{4}.</cmath>For this to be equal to <math>(n+5)q+17</math> for some integer <math>q</math>, it must be that<cmath>n^2(n+1)^2=4(n+5)q+4\cdot 17,</cmath>so<cmath>n^2(n+1)^2 \equiv 4 \cdot 17= 68\hskip-.2cm \pmod{n+5}.</cmath>But <math>n^2(n+1)^2 \equiv (-5)^2(-4)^2 = 400 \pmod{n+5}.</math> Thus <math>n^2(n+1)^2</math> is congruent to both <math>68</math> and <math>400,</math> which implies that <math>n+5</math> divides <math>400-68 = 332=2^2 \cdot 83</math>. Because <math>n+5 > 17</math>, the only choices for <math>n+5</math> are <math>83, 166,</math> and <math>332.</math> Checking all three cases verifies that <math>n=78</math> and <math>n=161</math> work, but <math>n=327</math> does not. The requested sum is <math>78+161 = 239</math>. | ||
+ | |||
+ | ==Solution 4 (Official MAA 2)== | ||
+ | The sum of the cubes of the integers from <math>1</math> through <math>n</math> is<cmath>\frac{n^2(n+1)^2}{4},</cmath>which, when divided by <math>n+5</math>, has quotient<cmath>Q=\frac14n^3 -\frac34n^2+4n-20 = \frac{n^2(n-3)}4+4n-20</cmath>with remainder <math>100.</math> If <math>n</math> is not congruent to <math>1\pmod4</math>, then <math>Q</math> is an integer, and<cmath>\frac{n^2(n+1)^2}{4} = (n+5)Q + 100 \equiv 17\pmod{n+5},</cmath>so <math>n+5</math> divides <math>100 - 17 =83</math>, and <math>n = 78</math>. If <math>n \equiv 1 \pmod4</math>, then <math>Q</math> is half of an integer, and letting <math>n = 4k+1</math> for some integer <math>k</math> gives<cmath>\frac{n^2(n+1)^2}{4} = 2(2k+3)Q + 100 \equiv 17\pmod{n+5}.</cmath>Thus <math>2k+3</math> divides <math>100-17 = 83</math>. It follows that <math>k=40</math>, and <math>n = 161</math>. The requested sum is <math>161 + 78 = 239</math>. | ||
+ | |||
+ | ==Solution 5== | ||
+ | Using the formula for <math>\sum_{k=1}^n k^3</math>, | ||
+ | <cmath>1^3 + 2^3 + 3^3 + ... + n^3 = \frac{n^2(n+1)^2}{4}</cmath> | ||
+ | Since <math>1^3 + 2^3 + 3^3 + ... + n^3</math> divided by <math>n + 5</math> has a remainder of <math>17</math>, | ||
+ | <cmath>\frac{n^2(n+1)^2}{4} \equiv 17\pmod {n + 5}</cmath> | ||
+ | Using the rules of modular arithmetic, | ||
+ | <cmath>n^2(n+1)^2 \equiv 68\pmod {n + 5}</cmath><cmath>n^2(n+1)^2 - 68\equiv 0\pmod {n + 5}</cmath> | ||
+ | Expanding the left hand side, | ||
+ | <cmath>n^4 + 2 n^3 + n^2 - 68\equiv 0\pmod {n + 5}</cmath> | ||
+ | This means that | ||
+ | <math>n^4 + 2 n^3 + n^2 - 68</math> is divisible by <math>{n + 5}</math>. | ||
+ | |||
+ | <cmath>(n + 5) | (n^4 + 2 n^3 + n^2 - 68)</cmath> | ||
+ | Dividing polynomials, | ||
+ | <cmath>\frac{n^4 + 2 n^3 + n^2 - 68}{n + 5}</cmath> | ||
+ | <cmath>= n^3 - 3 n^2 + 16n - 80 + \frac{332}{(n + 5)}</cmath> | ||
+ | <math>(n + 5)</math> <math>|</math> <math>(n^4 + 2 n^3 + n^2 - 68)</math> <math>\iff</math> <math>\frac{332}{(n + 5)}</math> <math>\in</math> <math>\mathbb{Z}</math> | ||
+ | <br><br> | ||
+ | <math>\frac{332}{(n + 5)}</math> <math>\in</math> | ||
+ | <math>\mathbb{Z}</math> <math>\iff</math> <math>(n + 5) = \pm 1, \pm 2, \pm 4, \pm 83, \pm 166, \pm 332</math> | ||
+ | <br><br> | ||
+ | Note that <math>n</math> <math>\in</math> <math>\mathbb{N}</math> and <math>n + 5 > 17</math> (because the remainder when dividing by <math>n + 5</math> is <math>17</math>, so <math>n + 5</math> must be greater than <math>17</math>), so all options <math>\leq 17</math> can be eliminated. | ||
+ | <cmath>(n + 5) = 83, 166, 332</cmath> | ||
+ | <cmath>n = 78, 161, 327</cmath> | ||
+ | Checking all 3 cases, <math>n = 78</math> and <math>n = 161</math> work; <math>n = 327</math> fails. | ||
+ | <br><br> | ||
+ | Therefore, the answer is <math>78 + 161 = \boxed{239}</math>. | ||
+ | <br><br> | ||
+ | ~ {TSun} ~ | ||
+ | |||
+ | == Solution 6 (similar ideas to Solution 1, but faster) == | ||
+ | As before, we note that <math>(5+a)^3 + (n-a)^3 \equiv (5+a)^3 - (n+5 - (n-a))^3 \equiv 0 \pmod {n+5}.</math> | ||
+ | Thus, we can pair up the terms from <math>5^3</math> to <math>n^3</math> and cancel them. We have to deal with two cases: | ||
+ | |||
+ | If <math>n</math> is even, then <math>5^3+6^3 + \cdots + n^3 \equiv 0 \pmod {n+5},</math> as there are an even number of terms and they pair and cancel. We thus get <math>1^2+2^3+3^3+4^3 = 100 \equiv 17 \pmod {n+5},</math> or <math>(n+5) | 83,</math> which yields <math>n=78.</math> | ||
+ | |||
+ | If <math>n</math> is odd, then <math>1^3+2^3+\cdots + n^3 \equiv 1^3+2^3+3^3+4^3+\left( \frac{n+5}{2} \right)^3 \equiv 17 \pmod {n+5}.</math> | ||
+ | Letting <math>k = \frac{n+5}{2}</math> yields <math>k^2 + 83 \equiv 0 \pmod {2k}.</math> However, this means that <math>83</math> is divisible by <math>k,</math> so <math>k=1,83.</math> | ||
+ | Plugging this back into <math>n</math> yields <math>n=2(83)-5 = 161</math> in the latter case. | ||
+ | |||
+ | Thus, the sum of all possible <math>n</math> is just <math>78+161 = \boxed{239}.</math> | ||
+ | |||
+ | - ccx09 | ||
+ | |||
+ | ==Video solution== | ||
+ | https://www.youtube.com/watch?v=87Mp0cdUtCU | ||
+ | ~ North America Math Contest Go Go Go | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/bz5N-jI2e0U?t=201 | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/bz5N-jI2e0U?t=201 | ||
+ | |||
+ | ==See Also== | ||
+ | {{AIME box|year=2020|n=II|num-b=9|num-a=11}} | ||
+ | {{MAA Notice}} |
Latest revision as of 18:09, 22 February 2022
Contents
- 1 Problem
- 2 Solution 1 (If you don't remember the formula for sum of cubes)
- 3 Solution 2 (using the sum of cubes formula)
- 4 Solution 3 (Official MAA 1)
- 5 Solution 4 (Official MAA 2)
- 6 Solution 5
- 7 Solution 6 (similar ideas to Solution 1, but faster)
- 8 Video solution
- 9 Video Solution
- 10 Video Solution
- 11 See Also
Problem
Find the sum of all positive integers such that when is divided by , the remainder is .
Solution 1 (If you don't remember the formula for sum of cubes)
We first note that since the remainder is and we are dividing by , must be greater than , meaning that has to be at least .
We then notice that we can pair the term with the term to factor it into using the sum of two cubes factorization (), which is divisible by . We can do the same for the term with the term, the term with the , and so on, which are all divisible by . However, when is odd, we will have a middle term that is not paired with any other terms, which is not necessarily divisible by . Thus, we have two cases:
is even
If is even, all terms that are greater than pair, as there are an even number of terms that are greater than . Therefore, all we need in order for the entire sequence to have a remainder of when divided by is to have a remainder of when divided by .
Evaluating as , all we need to be true is or that Thus, will be divisible by where . As is prime, must be equal to either or . If , we have that , which is not greater than or equal to , so that solution is extraneous.
If , we have that , which is , so one of our solutions is , and we are done with our first case.
is odd
If is odd, the only term that does not pair is the arithmetic mean of the numbers under the cube of the largest and smallest terms that would pair, or . Therefore, as all other terms that are pair, the requirement that we have is
Calculating and simplifying, we have that
Now, we multiply both sides by . However, since multiplication is not reversible in modular arithmetic, we need to check whether any solutions are extraneous after solving. The congruence that we now have is
As we know that is divisible by , what we need now is
We now check each solution to see whether it works.
If , would be less than , so none of these solutions work. If , would be even, so that solution does not work for this case. Therefore, the only three solutions we need to check for this case are when , , or . We plug these values into the congruence before we multiplied both sides by to check.
If , we would need Calculating and factoring out , we have that As the right parenthesis is odd and , we know that this solution works, so we have another solution: .
If , we would need As the left hand side is odd, but all multiples of is even, this solution is therefore extraneous.
If , we would need
Again, the left hand side is odd, and all multiples of are even, so this solution is extraneous.
Therefore, our final answer is .
~ CoolCarsOnTheRun
Solution 2 (using the sum of cubes formula)
The formula for the sum of cubes is as follows: So let's apply this to this problem.
Let . Then we have So, . Testing the cases, only fails. This leaves .
Solution 3 (Official MAA 1)
The sum of the cubes from 1 to is For this to be equal to for some integer , it must be thatsoBut Thus is congruent to both and which implies that divides . Because , the only choices for are and Checking all three cases verifies that and work, but does not. The requested sum is .
Solution 4 (Official MAA 2)
The sum of the cubes of the integers from through iswhich, when divided by , has quotientwith remainder If is not congruent to , then is an integer, andso divides , and . If , then is half of an integer, and letting for some integer givesThus divides . It follows that , and . The requested sum is .
Solution 5
Using the formula for , Since divided by has a remainder of , Using the rules of modular arithmetic, Expanding the left hand side, This means that is divisible by .
Dividing polynomials,
Note that and (because the remainder when dividing by is , so must be greater than ), so all options can be eliminated.
Checking all 3 cases, and work; fails.
Therefore, the answer is .
~ {TSun} ~
Solution 6 (similar ideas to Solution 1, but faster)
As before, we note that Thus, we can pair up the terms from to and cancel them. We have to deal with two cases:
If is even, then as there are an even number of terms and they pair and cancel. We thus get or which yields
If is odd, then Letting yields However, this means that is divisible by so Plugging this back into yields in the latter case.
Thus, the sum of all possible is just
- ccx09
Video solution
https://www.youtube.com/watch?v=87Mp0cdUtCU ~ North America Math Contest Go Go Go
Video Solution
https://youtu.be/bz5N-jI2e0U?t=201
Video Solution
https://youtu.be/bz5N-jI2e0U?t=201
See Also
2020 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 9 |
Followed by Problem 11 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.