Difference between revisions of "2017 AIME I Problems/Problem 13"
(→Solution 3) |
(→Solution 3) |
||
Line 46: | Line 46: | ||
Claim: <math>a^{3} \geq 3a^{2} + 3a + 1</math> for integer solutions exists when <math>a \geq 4</math>. | Claim: <math>a^{3} \geq 3a^{2} + 3a + 1</math> for integer solutions exists when <math>a \geq 4</math>. | ||
+ | |||
Proof: Let's plug in <math>a = 4</math> for our base case. We get: <math>64 \geq 48 + 12 + 1 = 61</math> which holds true. Hence, the inductive hypothesis is that <math>(a + 1)^{3} \geq 3(a + 1)^{2} + 3(a + 1) + 1</math> for all <math>a \geq 3</math>. In fact, we simplify to prove <math>a^{3} \geq 6a + 6</math> for all <math>a \geq 3</math>. Now, from our inductive assumption, we need to prove that <math>3a^{2} + 3a + 1 \geq 6a + 6</math>. Hence, <math>3a^{2} - 3a \geq 5</math> for all <math>a \geq 3</math>. Hence, we need to show <math>a^{2} - a \geq \frac{5}{3}</math> for all <math>a \geq 3</math>. But since we're proving this in the integer world, this is equivalent to proving that <math>a^{2} -a \geq 2</math> for all <math>a \geq 3</math>. Now we need to show that <math>a^{2} \geq a + 2</math>. Dividing by <math>a</math> because <math>a</math> is a positive integer means we have to show <math>a \geq 1 + \frac{2}{a}</math>. Now since <math>a \geq 3</math>, <math>\frac{2}{a} < 1</math> and so the <math>RHS</math> of the inequality can't even exceed <math>2</math> whereas the <math>LHS</math> of the inequality is already exceeding <math>2</math>. Therefore, the inductive hypothesis holds true and we are done. | Proof: Let's plug in <math>a = 4</math> for our base case. We get: <math>64 \geq 48 + 12 + 1 = 61</math> which holds true. Hence, the inductive hypothesis is that <math>(a + 1)^{3} \geq 3(a + 1)^{2} + 3(a + 1) + 1</math> for all <math>a \geq 3</math>. In fact, we simplify to prove <math>a^{3} \geq 6a + 6</math> for all <math>a \geq 3</math>. Now, from our inductive assumption, we need to prove that <math>3a^{2} + 3a + 1 \geq 6a + 6</math>. Hence, <math>3a^{2} - 3a \geq 5</math> for all <math>a \geq 3</math>. Hence, we need to show <math>a^{2} - a \geq \frac{5}{3}</math> for all <math>a \geq 3</math>. But since we're proving this in the integer world, this is equivalent to proving that <math>a^{2} -a \geq 2</math> for all <math>a \geq 3</math>. Now we need to show that <math>a^{2} \geq a + 2</math>. Dividing by <math>a</math> because <math>a</math> is a positive integer means we have to show <math>a \geq 1 + \frac{2}{a}</math>. Now since <math>a \geq 3</math>, <math>\frac{2}{a} < 1</math> and so the <math>RHS</math> of the inequality can't even exceed <math>2</math> whereas the <math>LHS</math> of the inequality is already exceeding <math>2</math>. Therefore, the inductive hypothesis holds true and we are done. | ||
Latest revision as of 19:55, 16 August 2025
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
Solution 3
Note that the problem is just asking for every , find the least
such that there lies a perfect cube in between of
and
for every
after that minimum including the minimum. We consider
first. Then, we need to find the least
such that for every
after this minimum
, including the minimum, there lies a perfect cube in between of
and
. Let's denote the range notation as
. Hence, we start with
to get the range of
. Clearly, no perfect cube lies between these numbers. Then we go to
to get
and here also nothing works. We can see that the perfect cubes are
. Because
can't lie between two positive integers, we need to find the minimum
such that
is between
and
. Clearly,
will yield this case. We have the range
. This works. We now list every
starting from
and see if all of these ranges host a perfect cube in between them. We have
works,
works
works, but
doesn't work. This is because the next perfect cube has to be
. Aha! Now we see the case. If we have a range in the following form
, this will clearly host a perfect cube between them which is
. But as we keep going, we need to put the next perfect cube after
into the range which is
. We know that the next range after
is just
because we double everything. Hence,
must be in this range. If the perfect cube in between
and
is of the form
, we know that this added constant
is greater than or equal to
. Hence, we let
to solve
and for integer solutions, we claim the answer is
. We can prove this by induction.
Claim: for integer solutions exists when
.
Proof: Let's plug in for our base case. We get:
which holds true. Hence, the inductive hypothesis is that
for all
. In fact, we simplify to prove
for all
. Now, from our inductive assumption, we need to prove that
. Hence,
for all
. Hence, we need to show
for all
. But since we're proving this in the integer world, this is equivalent to proving that
for all
. Now we need to show that
. Dividing by
because
is a positive integer means we have to show
. Now since
,
and so the
of the inequality can't even exceed
whereas the
of the inequality is already exceeding
. Therefore, the inductive hypothesis holds true and we are done.
What we have just shown now is that . Now note that the minimum range we found that worked was
where
. We plug in
to get
and hence
. We can now apply the same procedure to the other numbers and finish as the above solutions.
~ilikemath247365
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 |
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions.