Difference between revisions of "2020 AIME II Problems/Problem 10"
Mathkiddie (talk | contribs) |
(→Solution 3 (Official MAA 2)) |
||
Line 27: | Line 27: | ||
==Solution 3 (Official MAA 2)== | ==Solution 3 (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>. | + | The sum of the cubes of the integers from <math>1</math> through <math>n</math> is<cmath>1^3+2^3+\cdots+n^3=\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 4== | ==Solution 4== |
Revision as of 02:19, 22 January 2024
Contents
[hide]Problem
Find the sum of all positive integers such that when is divided by , the remainder is .
Solution 1
The formula for the sum of cubes, also known as Nicomachus's Theorem, is as follows: for any positive integer .
So let's apply this to this problem.
Let . Then we have So, . Testing the cases, only fails. This leaves .
and formatting adjustments and intermediate steps for clarification by Technodoggo.
Solution 2 (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 3 (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 4
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 5 (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 by OmegaLearn
https://youtu.be/LqrXinQbk1Q?t=1253
~ pi_is_3.14
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
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.