2017 AIME I Problems/Problem 13

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*n$ .

Thats because $\sqrt[3]{m*n} - \sqrt[3]{n} \ge 2\sqrt[3]{n} - \sqrt[3]{n} = \sqrt[3]{n} \ge 1$ , so k exists between $\sqrt[3]{m*n}$ and $\sqrt[3]{n}$

$\sqrt[3]{n} < k \le \sqrt[3]{m*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

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

Page

Toolbox

Search

2017 AIME I Problems/Problem 13

Contents

Problem 13

Solution 1

Solution 2

See Also