2012 AIME II Problem 10

Question

Find the number of positive integers

n

less than

1000

for which there exists a positive real number

x

such that

n = x\lfloor x \rfloor.

Note:

\lfloor x \rfloor

is the greatest integer less than or equal to

x.

Answer

Answer: 496

Concepts:floor and ceiling functions counting integers in a range

Difficulty rating: 2460

Small hint:

Fix

\lfloor x \rfloor = a;

as

x

runs from

a

to

a + 1,

the product

x\lfloor x \rfloor

sweeps through the integers from

a^2

to

a^2 + a - 1

Big hint:

Each

a

contributes exactly

a

values of

n;

sum over all

a

whose values stay below

1000

Solution:

Fix

\lfloor x \rfloor = a \ge 1.

For

a \le x \lt a + 1

the product

n = ax

ranges over

[a^2, a^2 + a),

and every integer

n

in that interval is achieved by

x = \frac{n}{a}

(which indeed has floor

a

). So each

a

contributes exactly

a

values of

n,

namely

a^2, a^2 + 1, \ldots, a^2 + a - 1.

For

a = 31

the largest value is

31^2 + 30 = 991 \lt 1000,

so all values through

a = 31

qualify, while

a = 32

already starts at

1024.

The count is

1 + 2 + \cdots + 31 = \frac{31 \cdot 32}{2} = 496.