2009 AIME I Problem 6

Attempt Problem 6 of the 2009 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 2009 AIME I solutions, or check the answer key.

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

6.

How many positive integers NN less than 10001000 are there such that the equation xx=Nx^{\lfloor x \rfloor} = N has a solution for x?x? (The notation x\lfloor x \rfloor denotes the greatest integer that is less than or equal to x.x.)

Answer: 412
Concepts:floor and ceiling functionscounting integers in a rangecasework
Difficulty rating: 2390
Solution:

Suppose x=k\lfloor x \rfloor = k for a positive integer k.k. As xx runs over [k,k+1),[k, k+1), the value xkx^k increases continuously from kkk^k toward (k+1)k,(k+1)^k, so the attainable integers NN are exactly those with kkN(k+1)k1:k^k \le N \le (k+1)^k - 1: there are (k+1)kkk(k+1)^k - k^k of them, and these ranges are disjoint for different k.k. (Values of xx below 11 produce no new positive integers, since x0=1x^0 = 1 is already attained.)

For k=1,2,3,4k = 1, 2, 3, 4 the counts are 21=1,2 - 1 = 1, 94=5,9 - 4 = 5, 6427=37,64 - 27 = 37, and 625256=369,625 - 256 = 369, and every such NN is at most 624<1000.624 \lt 1000. For k=5k = 5 the smallest value is 55=3125>1000.5^5 = 3125 \gt 1000.

The total is 1+5+37+369=412.1 + 5 + 37 + 369 = 412.

← Problem 5#5
Full Exam

Problem 6 in Other Years