Difference between revisions of "2020 AIME II Problems/Problem 10"
m (improved some explanation and readability) |
Cevatheorom (talk | contribs) (→Problem) |
||
(11 intermediate revisions by 10 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 == |
− | + | The formula for the sum of cubes, also known as Nicomachus's Theorem, is as follows: | |
+ | <cmath>1^3+2^3+3^3+\dots+k^3=(1+2+3+\dots+k)^2=\left(\frac{k(k+1)}{2}\right)^2</cmath> | ||
+ | for any positive integer <math>k</math>. | ||
− | + | So let's apply this to this problem. | |
− | |||
− | |||
− | |||
− | + | Let <math>m=n+5</math>. Then we have | |
− | + | <cmath>\begin{align*} | |
− | + | 1^3+2^3+3^3+\dots+(m-5)^3&\equiv 17 \mod m \\ | |
− | + | \left(\frac{(m-5)(m-4)}{2}\right)^2&\equiv 17 \mod m \\ | |
− | + | \left(\dfrac{m(m-9)+20}2\right)^2&\equiv 17\mod m \\ | |
+ | \left(\dfrac{20}2\right)^2&\equiv 17\mod m \\ | ||
+ | \frac{400}{4}&\equiv 17 \mod m \\ | ||
+ | 332 &\equiv 0 \mod m \\ | ||
+ | \end{align*}</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>. | ||
− | + | <math>\LaTeX</math> and formatting adjustments and intermediate steps for clarification by Technodoggo. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | ==Solution 2 (Official MAA 1)== | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | ==Solution 2 | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
The sum of the cubes from 1 to <math>n</math> is | 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>. | <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 | + | ==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 | + | ==Solution 4== |
Using the formula for <math>\sum_{k=1}^n k^3</math>, | 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> | <cmath>1^3 + 2^3 + 3^3 + ... + n^3 = \frac{n^2(n+1)^2}{4}</cmath> | ||
Line 94: | Line 59: | ||
~ {TSun} ~ | ~ {TSun} ~ | ||
− | == Solution | + | == Solution 5 (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> | 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: | 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: | ||
Line 107: | Line 72: | ||
- ccx09 | - ccx09 | ||
+ | |||
+ | == Video Solution by OmegaLearn == | ||
+ | https://artofproblemsolving.com/alcumus/problem | ||
+ | |||
+ | ~ pi_is_3.14 | ||
==Video solution== | ==Video solution== | ||
https://www.youtube.com/watch?v=87Mp0cdUtCU | https://www.youtube.com/watch?v=87Mp0cdUtCU | ||
− | ~ North America Math Contest Go Go Go | + | ~ North America Math Contest Go Go Go |
− | |||
− | |||
− | |||
==Video Solution== | ==Video Solution== | ||
Line 121: | Line 88: | ||
{{AIME box|year=2020|n=II|num-b=9|num-a=11}} | {{AIME box|year=2020|n=II|num-b=9|num-a=11}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] |
Latest revision as of 10:13, 26 July 2024
Contents
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 that
so
But
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
is
which, when divided by
, has quotient
with remainder
If
is not congruent to
, then
is an integer, and
so
divides
, and
. If
, then
is half of an integer, and letting
for some integer
gives
Thus
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://artofproblemsolving.com/alcumus/problem
~ 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.