Difference between revisions of "2017 AIME I Problems/Problem 13"
(→Solution) |
(→Solution) |
||
Line 5: | Line 5: | ||
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. | ||
− | Lemma 2: If the range <math>(n,mn]</math> includes two cubes, <math>(p,mp]</math> will always contain at least one cube for all | + | Lemma 2: If the range <math>(n,mn]</math> includes two cubes, <math>(p,mp]</math> will always contain at least one cube for all <math>p</math> in <math>[n,+\infty)</math>. |
− | If <math>m=14</math>, the range <math>(1,14]</math> includes one cube. The range <math>(2,28]</math> includes 2 cubes, which fulfills the Lemma. Since <math>n=1</math> also included a cube, we can assume that <math>Q(m)=1</math> for all <math>m>14</math>. Two groups of 1000 are included in the sum modulo 1000. They do not count since <math>Q(m)=1</math> for all of them, therefore <cmath>\sum_{m = 2}^{2017} Q(m) | + | If <math>m=14</math>, the range <math>(1,14]</math> includes one cube. The range <math>(2,28]</math> includes 2 cubes, which fulfills the Lemma. Since <math>n=1</math> also included a cube, we can assume that <math>Q(m)=1</math> for all <math>m>14</math>. Two groups of 1000 are included in the sum modulo 1000. They do not count since <math>Q(m)=1</math> for all of them, therefore <cmath>\sum_{m = 2}^{2017} Q(m) \equiv \sum_{m = 2}^{17} Q(m) \mod 1000</cmath> |
Now that we know this we will find the smallest <math>n</math> that causes <math>(n,mn]</math> to contain two cubes and work backwards (recursion) until there is no cube in <math>(n,mn]</math>. | Now that we know this we will find the smallest <math>n</math> that causes <math>(n,mn]</math> to contain two cubes and work backwards (recursion) until there is no cube in <math>(n,mn]</math>. |
Revision as of 23:58, 8 March 2017
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
Lemma 1: The ratio between and
decreases as
increases.
Lemma 2: If the range includes two cubes,
will always contain at least one cube 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
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.