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 "2020 AIME II Problems/Problem 10"

(→‎Solution 6 (similar ideas to Solution 1, but faster))
m (Undo revision 223705 by Cevatheorom (talk))
(Tag: Undo)
 
(18 intermediate revisions by 15 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 (If you don't remember the formula for sum of cubes) ==
+
==Solution 1 ==
−
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>.
+
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>.  
  
−
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 formula (<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:
+
So let's apply this to this problem.
−
<br><br>
 
−
<math>\textbf{CASE 1: } n</math> is even <br>
 
−
If <math>n</math> is even, all terms that are greater than <math>4^3</math> pair, as there are an even number of terms that are greater than <math>4^3</math>. Therefore, all we need in order for the entire sequence to have a remainder of <math>17</math> when divided by <math>n+5</math> is <math>1^3+2^3+3^3+4^3</math> to have a remainder of <math>17</math> when divided by <math>n+5</math>.
 
  
−
Evaluating <math>1^3+2^3+3^3+4^3</math> as <math>100</math>, all we need to be true is
+
Let <math>m=n+5</math>. Then we have
−
<cmath>100\equiv 17\pmod {n+5},</cmath>
+
<cmath>\begin{align*}
−
or that
+
1^3+2^3+3^3+\dots+(m-5)^3&\equiv 17 \mod m \\
−
<cmath>83\equiv 0\pmod {n+5}.</cmath>
+
\left(\frac{(m-5)(m-4)}{2}\right)^2&\equiv 17 \mod m \\
−
Thus, <math>83</math> will be divisible by <math>n+5</math> where <math>n\geq 13</math>. As <math>83</math> is prime, <math>n+5</math> must be equal to either <math>1</math> or <math>83</math>. If <math>n+5=1</math>, we have that <math>n=-4</math>, which is not greater than or equal to <math>13</math>, so that solution is extraneous.
+
\left(\dfrac{m(m-9)+20}2\right)^2&\equiv 17\mod m \\
−
 
+
\left(\dfrac{20}2\right)^2&\equiv 17\mod m \\
−
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.
+
\frac{400}{4}&\equiv 17 \mod m \\
−
<br><br>
+
332 &\equiv 0 \mod m \\
−
<math>\textbf{CASE 2: } n</math> is odd
+
\end{align*}</cmath>
−
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
+
So, <math>m\in\{83,166,332\}</math>. Testing the cases, only <math>332</math> fails. This leaves <math>78+161=\boxed{239}</math>.  
−
<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
 
−
<cmath>83+\left(\frac{n+5}{2}\right)^3\equiv 0\pmod {n+5}.</cmath>
 
−
Now, we multiply both sides by <math>8</math>. 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
 
−
<cmath>8\cdot 83+(n+5)^3\equiv 0\pmod {n+5}.</cmath>
 
−
As we know that <math>(n+5)^3</math> is divisible by <math>n+5</math>, what we need now is
 
−
<cmath>8\cdot 83\equiv 0\pmod {n+5}.</cmath>
 
−
We now check each solution to see whether it works.
 
−
 
 
−
If <math>n+5=1, 2, 4, 8</math>, <math>n</math> would be less than <math>13</math>, so none of these solutions work. If <math>n+5=83</math>, <math>n</math> 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 <math>n+5=166</math>, <math>n+5=332</math>, or <math>n+5=664</math>. We plug these values into the congruence before we multiplied both sides by <math>8</math> to check.
 
−
 
 
−
If <math>n+5=166</math>, we would need
 
−
<cmath>83+\left(\frac{166}{2}\right)^3\equiv 0\pmod {166}.</cmath>
 
−
Calculating and factoring out <math>83</math>, we have that
 
−
<cmath>83(1+83\cdot 83)\equiv 0\pmod {166}.</cmath>
 
−
As the right parenthesis is odd and <math>166=83\cdot 2</math>, we know that this solution works, so we have another solution: <math>n=166-5=161</math>.
 
  
−
If <math>n+5=332</math>, we would need
+
<math>\LaTeX</math> and formatting adjustments and intermediate steps for clarification by Technodoggo.  
−
<cmath>83+\left(\frac{332}{2}\right)^3=83+166^3\equiv 0\pmod {322}.</cmath>
 
−
As the left hand side is odd, but all multiples of <math>322</math> is even, this solution is therefore extraneous.
 
  
−
If <math>n+5=664</math>, we would need
+
==Solution 2 (Official MAA 1)==
−
<cmath>83+\left(\frac{664}{2}\right)^3=83+332^3\equiv 0\pmod {664}.</cmath>
 
−
Again, the left hand side is odd, and all multiples of <math>664</math> are even, so this solution is extraneous.
 
−
<br><br>
 
−
Therefore, our final answer is <math>78+161=\boxed{239}</math>.
 
−
<br><br>
 
−
~ CoolCarsOnTheRun
 
−
 
 
−
==Solution 2 (w/ formula)==
 
−
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
 
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 4 (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 5==
+
==Solution 4==
−
Using the formula for  <math>\sum_{k=1}^n  n^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>
 
Since <math>1^3 + 2^3 + 3^3 + ... + n^3</math> divided by <math>n + 5</math> has a remainder of <math>17</math>,
 
Since <math>1^3 + 2^3 + 3^3 + ... + n^3</math> divided by <math>n + 5</math> has a remainder of <math>17</math>,
Line 94: Line 59:
 
~ {TSun} ~
 
~ {TSun} ~
  
−
== Solution 6 (similar ideas to Solution 1, but faster) ==
+
== 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==
 +
https://www.youtube.com/watch?v=87Mp0cdUtCU
 +
~ North America Math Contest Go Go Go
  
 
==Video Solution==
 
==Video Solution==
Line 114: 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 13:19, 21 October 2024

Problem

Find the sum of all positive integers $n$ such that when $1^3+2^3+3^3+\cdots +n^3$ is divided by $n+5$, the remainder is $17$.

Solution 1

The formula for the sum of cubes, also known as Nicomachus's Theorem, is as follows: \[1^3+2^3+3^3+\dots+k^3=(1+2+3+\dots+k)^2=\left(\frac{k(k+1)}{2}\right)^2\] for any positive integer $k$.

So let's apply this to this problem.

Let $m=n+5$. Then we have \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*} So, $m\in\{83,166,332\}$. Testing the cases, only $332$ fails. This leaves $78+161=\boxed{239}$.

$\LaTeX$ and formatting adjustments and intermediate steps for clarification by Technodoggo.

Solution 2 (Official MAA 1)

The sum of the cubes from 1 to $n$ is \[1^3+2^3+\cdots+n^3=\frac{n^2(n+1)^2}{4}.\]For this to be equal to $(n+5)q+17$ for some integer $q$, it must be that\[n^2(n+1)^2=4(n+5)q+4\cdot 17,\]so\[n^2(n+1)^2 \equiv 4 \cdot 17= 68\hskip-.2cm \pmod{n+5}.\]But $n^2(n+1)^2 \equiv (-5)^2(-4)^2 = 400 \pmod{n+5}.$ Thus $n^2(n+1)^2$ is congruent to both $68$ and $400,$ which implies that $n+5$ divides $400-68 = 332=2^2 \cdot 83$. Because $n+5 > 17$, the only choices for $n+5$ are $83, 166,$ and $332.$ Checking all three cases verifies that $n=78$ and $n=161$ work, but $n=327$ does not. The requested sum is $78+161 = 239$.

Solution 3 (Official MAA 2)

The sum of the cubes of the integers from $1$ through $n$ is\[1^3+2^3+\cdots+n^3=\frac{n^2(n+1)^2}{4},\]which, when divided by $n+5$, has quotient\[Q=\frac14n^3 -\frac34n^2+4n-20 = \frac{n^2(n-3)}4+4n-20\]with remainder $100.$ If $n$ is not congruent to $1\pmod4$, then $Q$ is an integer, and\[\frac{n^2(n+1)^2}{4} = (n+5)Q + 100 \equiv 17\pmod{n+5},\]so $n+5$ divides $100 - 17 =83$, and $n = 78$. If $n \equiv 1 \pmod4$, then $Q$ is half of an integer, and letting $n = 4k+1$ for some integer $k$ gives\[\frac{n^2(n+1)^2}{4} = 2(2k+3)Q + 100 \equiv 17\pmod{n+5}.\]Thus $2k+3$ divides $100-17 = 83$. It follows that $k=40$, and $n = 161$. The requested sum is $161 + 78 = 239$.

Solution 4

Using the formula for $\sum_{k=1}^n k^3$, \[1^3 + 2^3 + 3^3 + ... + n^3 = \frac{n^2(n+1)^2}{4}\] Since $1^3 + 2^3 + 3^3 + ... + n^3$ divided by $n + 5$ has a remainder of $17$, \[\frac{n^2(n+1)^2}{4} \equiv 17\pmod {n + 5}\] Using the rules of modular arithmetic, \[n^2(n+1)^2 \equiv 68\pmod {n + 5}\]\[n^2(n+1)^2 - 68\equiv 0\pmod {n + 5}\] Expanding the left hand side, \[n^4 + 2 n^3 + n^2 - 68\equiv 0\pmod {n + 5}\] This means that $n^4 + 2 n^3 + n^2 - 68$ is divisible by ${n + 5}$.

\[(n + 5) | (n^4 + 2 n^3 + n^2 - 68)\] Dividing polynomials, \[\frac{n^4 + 2 n^3 + n^2 - 68}{n + 5}\] \[= n^3 - 3 n^2 + 16n - 80 + \frac{332}{(n + 5)}\] $(n + 5)$ $|$ $(n^4 + 2 n^3 + n^2 - 68)$ $\iff$ $\frac{332}{(n + 5)}$ $\in$ $\mathbb{Z}$

$\frac{332}{(n + 5)}$ $\in$ $\mathbb{Z}$ $\iff$ $(n + 5) = \pm 1, \pm 2, \pm 4, \pm 83, \pm 166, \pm 332$

Note that $n$ $\in$ $\mathbb{N}$ and $n + 5 > 17$ (because the remainder when dividing by $n + 5$ is $17$, so $n + 5$ must be greater than $17$), so all options $\leq 17$ can be eliminated. \[(n + 5) = 83, 166, 332\] \[n = 78, 161, 327\] Checking all 3 cases, $n = 78$ and $n = 161$ work; $n = 327$ fails.

Therefore, the answer is $78 + 161 = \boxed{239}$.

~ {TSun} ~

Solution 5 (similar ideas to Solution 1, but faster)

As before, we note that $(5+a)^3 + (n-a)^3 \equiv (5+a)^3 - (n+5 - (n-a))^3 \equiv 0 \pmod {n+5}.$ Thus, we can pair up the terms from $5^3$ to $n^3$ and cancel them. We have to deal with two cases:

If $n$ is even, then $5^3+6^3 + \cdots + n^3 \equiv 0 \pmod {n+5},$ as there are an even number of terms and they pair and cancel. We thus get $1^2+2^3+3^3+4^3 = 100 \equiv 17 \pmod {n+5},$ or $(n+5) | 83,$ which yields $n=78.$

If $n$ is odd, then $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}.$ Letting $k = \frac{n+5}{2}$ yields $k^2 + 83 \equiv 0 \pmod {2k}.$ However, this means that $83$ is divisible by $k,$ so $k=1,83.$ Plugging this back into $n$ yields $n=2(83)-5 = 161$ in the latter case.

Thus, the sum of all possible $n$ is just $78+161 = \boxed{239}.$

- 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_10&oldid=230269"