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 "2017 AIME I Problems/Problem 13"

m
m (→‎Solution 2)
 
(10 intermediate revisions by 4 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 ratios 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 integers in <math>[n,+\infty)</math>.
+
Lemma 2: If the range <math>(n,mn]</math> includes <math>y</math> cubes, <math>(p,mp]</math> will always contain at least <math>y-1</math> cubes 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) = \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) \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>.
 +
 
 +
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}\hspace{2 mm}QED\hspace{2 mm} \blacksquare</math>
 +
 
 +
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

Problem 13

For every $m \geq 2$, let $Q(m)$ be the least positive integer with the following property: For every $n \geq Q(m)$, there is always a perfect cube $k^3$ in the range $n < k^3 \leq m \cdot n$. Find the remainder when \[\sum_{m = 2}^{2017} Q(m)\]is divided by 1000.

Solution 1

Lemma 1: The ratio between $k^3$ and $(k+1)^3$ decreases as $k$ increases.

Lemma 2: If the range $(n,mn]$ includes $y$ cubes, $(p,mp]$ will always contain at least $y-1$ cubes for all $p$ in $[n,+\infty)$.

If $m=14$, the range $(1,14]$ includes one cube. The range $(2,28]$ includes 2 cubes, which fulfills the Lemma. Since $n=1$ also included a cube, we can assume that $Q(m)=1$ for all $m>14$. Two groups of 1000 are included in the sum modulo 1000. They do not count since $Q(m)=1$ for all of them, therefore \[\sum_{m = 2}^{2017} Q(m) \equiv \sum_{m = 2}^{17} Q(m) \mod 1000\]

Now that we know this we will find the smallest $n$ that causes $(n,mn]$ to contain two cubes and work backwards (recursion) until there is no cube in $(n,mn]$.

For $m=2$ there are two cubes in $(n,2n]$ for $n=63$. There are no cubes in $(31,62]$ but there is one in $(32,64]$. Therefore $Q(2)=32$.

For $m=3$ there are two cubes in $(n,3n]$ for $n=22$. There are no cubes in $(8,24]$ but there is one in $(9,27]$. Therefore $Q(3)=9$.

For $m$ in $\{4,5,6,7\}$ there are two cubes in $(n,4n]$ for $n=7$. There are no cubes in $(1,4]$ but there is one in $(2,8]$. Therefore $Q(4)=2$, and the same for $Q(5)$, $Q(6)$, and $Q(7)$ for a sum of $8$.

For all other $m$ there is one cube in $(1,8]$, $(2,16]$, $(3,24]$, and there are two in $(4,32]$. Therefore, since there are 10 values of $m$ in the sum, this part sums to $10$.

When the partial sums are added, we get $\boxed{059}\hspace{2 mm}QED\hspace{2 mm} \blacksquare$

This solution is brought to you by a1b2

Solution 2

We claim that $Q(m) = 1$ when $m \ge 8$.

When $m \ge 8$, for every $n \ge Q(m) = 1$, we need to prove there exists an integer $k$, such that $n < k^3 \le m \cdot n$.

That's because $\sqrt[3]{m \cdot n} - \sqrt[3]{n} \ge 2\sqrt[3]{n} - \sqrt[3]{n} = \sqrt[3]{n} \ge 1$, so k exists between $\sqrt[3]{m \cdot n}$ and $\sqrt[3]{n}$

$\sqrt[3]{n} < k \le \sqrt[3]{m \cdot n}$.

We can then hand evaluate $Q(m)$ for $m = 2,3,4,5,6,7$, and get $Q(2) = 32$, $Q(3) = 9$, and all the others equal 2.

There are a total of 2010 integers from 8 to 2017.

\[\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\]

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_AIME_I_Problems/Problem_13&oldid=219573"