Difference between revisions of "2017 AIME I Problems/Problem 13"
m |
(Finally used the word Lemma correctly) |
||
Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
− | Lemma 1: The | + | 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 integers in <math>[n,+\infty)</math>. | 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 integers 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) = \sum_{m = 2}^{17} Q(m)</cmath> | 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) = \sum_{m = 2}^{17} Q(m)</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>. | ||
+ | |||
+ | For <math>m=2</math> there are two cubes in <math>(n,2n]</math> for <math>n=63</math>. There are no cubes in <math>(31,62]</math> but there is one in <math>(32,64]</math>. Therefore <math>Q(2)=32</math>. | ||
+ | |||
+ | For <math>m=3</math> there are two cubes in <math>(n,3n]</math> for <math>n=22</math>. There are no cubes in <math>(8,24]</math> but there is one in <math>(9,27]</math>. Therefore <math>Q(3)=9</math>. | ||
+ | |||
+ | For <math>m</math> in <math>\{4,5,6,7\}</math> there are two cubes in <math>(n,4n]</math> for <math>n=7</math>. There are no cubes in <math>(1,4]</math> but there is one in <math>(2,8]</math>. Therefore <math>Q(4)=2</math>, and the same for <math>Q(5)</math>, <math>Q(6)</math>, and <math>Q(7)</math> for a sum of <math>8</math>. | ||
+ | |||
+ | For all other <math>m</math> there is one cube in <math>(1,8]</math>, <math>(2,16]</math>, <math>(3,24]</math>, and there are two in <math>(4,32]</math>. Therefore, since there are 10 values of <math>m</math> in the sum, this part sums to <math>10</math>. | ||
+ | |||
+ | When the partial sums are added, we get <math>\boxed{059}</math>. | ||
==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}} |
Revision as of 20:45, 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 integers 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 .
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.