Difference between revisions of "2017 AIME I Problems/Problem 13"
(→Solution) |
Lucaso dabs (talk | contribs) m (→Solution 2) |
||
(5 intermediate revisions by 3 users not shown) | |||
Line 2: | Line 2: | ||
For every <math>m \geq 2</math>, let <math>Q(m)</math> be the least positive integer with the following property: For every <math>n \geq Q(m)</math>, there is always a perfect cube <math>k^3</math> in the range <math>n < k^3 \leq m \cdot n</math>. Find the remainder when <cmath>\sum_{m = 2}^{2017} Q(m)</cmath>is divided by 1000. | For every <math>m \geq 2</math>, let <math>Q(m)</math> be the least positive integer with the following property: For every <math>n \geq Q(m)</math>, there is always a perfect cube <math>k^3</math> in the range <math>n < k^3 \leq m \cdot n</math>. Find the remainder when <cmath>\sum_{m = 2}^{2017} Q(m)</cmath>is divided by 1000. | ||
− | ==Solution== | + | ==Solution 1== |
Lemma 1: The ratio between <math>k^3</math> and <math>(k+1)^3</math> decreases as <math>k</math> increases. | Lemma 1: The ratio between <math>k^3</math> and <math>(k+1)^3</math> decreases as <math>k</math> increases. | ||
Line 22: | Line 22: | ||
This solution is brought to you by [[User:a1b2|a1b2]] | This solution is brought to you by [[User:a1b2|a1b2]] | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | We claim that <math>Q(m) = 1</math> when <math>m \ge 8</math>. | ||
+ | |||
+ | When <math>m \ge 8</math>, for every <math>n \ge Q(m) = 1</math>, we need to prove there exists an integer <math>k</math>, such that <math>n < k^3 \le m \cdot n</math>. | ||
+ | |||
+ | That's because <math>\sqrt[3]{m \cdot n} - \sqrt[3]{n} \ge 2\sqrt[3]{n} - \sqrt[3]{n} = \sqrt[3]{n} \ge 1</math>, so k exists between <math>\sqrt[3]{m \cdot n}</math> and <math>\sqrt[3]{n}</math> | ||
+ | |||
+ | <math>\sqrt[3]{n} < k \le \sqrt[3]{m \cdot n}</math>. | ||
+ | |||
+ | We can then hand evaluate <math>Q(m)</math> for <math>m = 2,3,4,5,6,7</math>, and get <math>Q(2) = 32</math>, <math>Q(3) = 9</math>, and all the others equal 2. | ||
+ | |||
+ | There are a total of 2010 integers from 8 to 2017. | ||
+ | |||
+ | <cmath>\sum_{m = 2}^{2017} Q(m) \equiv \sum_{m = 2}^{7} Q(m) + 2010 \equiv 32+9+2+2+2+2+10 = \boxed{059} \mod 1000</cmath> | ||
+ | |||
+ | -AlexLikeMath | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2017|n=I|num-b=12|num-a=14}} | {{AIME box|year=2017|n=I|num-b=12|num-a=14}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 10:45, 22 May 2024
Contents
Problem 13
For every , let be the least positive integer with the following property: For every , there is always a perfect cube in the range . Find the remainder when is divided by 1000.
Solution 1
Lemma 1: The ratio between and decreases as increases.
Lemma 2: If the range includes cubes, will always contain at least cubes for all in .
If , the range includes one cube. The range includes 2 cubes, which fulfills the Lemma. Since also included a cube, we can assume that for all . Two groups of 1000 are included in the sum modulo 1000. They do not count since for all of them, therefore
Now that we know this we will find the smallest that causes to contain two cubes and work backwards (recursion) until there is no cube in .
For there are two cubes in for . There are no cubes in but there is one in . Therefore .
For there are two cubes in for . There are no cubes in but there is one in . Therefore .
For in there are two cubes in for . There are no cubes in but there is one in . Therefore , and the same for , , and for a sum of .
For all other there is one cube in , , , and there are two in . Therefore, since there are 10 values of in the sum, this part sums to .
When the partial sums are added, we get
This solution is brought to you by a1b2
Solution 2
We claim that when .
When , for every , we need to prove there exists an integer , such that .
That's because , so k exists between and
.
We can then hand evaluate for , and get , , and all the others equal 2.
There are a total of 2010 integers from 8 to 2017.
-AlexLikeMath
See Also
2017 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
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.