2017 AIME I Problem 13

Attempt Problem 13 of the 2017 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2017 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

13.

For every m≥2,m \ge 2, let Q(m)Q(m) be the least positive integer with the following property: For every n≥Q(m),n \ge Q(m), there is always a perfect cube k3k^3 in the range n<k3≤m⋅n.n \lt k^3 \le m \cdot n. Find the remainder when ∑m=22017Q(m)\sum_{m=2}^{2017} Q(m) is divided by 1000.1000.

Answer: 59
Concepts:perfect powerbounding to limit casescasework
Difficulty rating: 3160
Small Hint:

The ratio of consecutive cubes is (1+1k)3,\left(1 + \frac{1}{k}\right)^3, which shrinks as kk grows, so only small mm can have Q(m)>1Q(m) \gt 1

Big Hint:

Q(m)=1Q(m) = 1 for every m≥8;m \ge 8; for m=2,…,7m = 2, \ldots, 7 find the last nn where the interval (n,mn](n, mn] skips a cube, using gaps like (27,64)(27, 64) and (8,27)(8, 27)

Solution:

If k3≤n<(k+1)3,k^3 \le n \lt (k+1)^3, then the interval (n,mn](n, mn] contains the cube (k+1)3(k+1)^3 as long as (k+1)3≤mk3,(k+1)^3 \le m k^3, i.e. (1+1k)3≤m.\left(1 + \frac{1}{k}\right)^3 \le m. Since (1+1k)3≤8\left(1 + \frac{1}{k}\right)^3 \le 8 for all k≥1,k \ge 1, every m≥8m \ge 8 has Q(m)=1.Q(m) = 1.

For 4≤m≤7:4 \le m \le 7: n=1n = 1 fails since (1,m](1, m] contains no cube, but for n≥2n \ge 2 the interval works: 8≤4n8 \le 4n covers 2≤n≤7,2 \le n \le 7, and (1+1k)3≤278<4\left(1 + \frac{1}{k}\right)^3 \le \frac{27}{8} \lt 4 covers k≥2.k \ge 2. So Q(4)=Q(5)Q(4) = Q(5) =Q(6)=Q(7)=2.= Q(6) = Q(7) = 2. For m=3:m = 3: n=8n = 8 fails (no cube in (8,24](8, 24]), while 27≤3n27 \le 3n covers 9≤n≤269 \le n \le 26 and (43)3<3\left(\frac{4}{3}\right)^3 \lt 3 covers k≥3,k \ge 3, so Q(3)=9.Q(3) = 9. For m=2:m = 2: n=31n = 31 fails (no cube in (31,62](31, 62]), while 64≤2n64 \le 2n covers 32≤n≤6332 \le n \le 63 and (54)3<2\left(\frac{5}{4}\right)^3 \lt 2 covers k≥4,k \ge 4, so Q(2)=32.Q(2) = 32.

Therefore ∑m=22017Q(m)=32+9+4⋅2+2010⋅1=2059, \begin{aligned} &\sum_{m=2}^{2017} Q(m) \\ &\quad = 32 + 9 + 4 \cdot 2 + 2010 \cdot 1 \\ &\quad = 2059, \end{aligned} and the remainder is 59.59.

Problem 12#12
Full Exam

Problem 13 in Other Years