2007 AIME I Problem 11

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

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

11.

For each positive integer

p,

let

b(p)

denote the unique positive integer

k

such that

|k - \sqrt{p}| \lt \frac{1}{2}.

For example,

b(6) = 2

and

b(23) = 5.

If

S = \sum_{p=1}^{2007} b(p),

find the remainder when

S

is divided by

1000.

Answer

Answer: 955

Concepts:floor and ceiling functions sum of first n squares counting integers in a range

Difficulty rating: 2610

Small hint:

b(p) = k

exactly when

k^2 - k + 1 \le p \le k^2 + k,

a block of

2k

values of

p

Big hint:

Complete blocks for

k \le 44

cover

p \le 1980;

every remaining

p

up to

2007

has

b(p) = 45

Solution:

For a positive integer

k,

the condition

|k - \sqrt{p}| \lt \frac{1}{2}

means

\left(k - \frac{1}{2}\right)^2 \lt p \lt \left(k + \frac{1}{2}\right)^2,

which for integers

p

is exactly

k^2 - k + 1 \le p \le k^2 + k.

So

b(p) = k

for precisely

2k

values of

p.

Since

44^2 + 44 = 1980,

the blocks

k = 1, \ldots, 44

exactly cover

p \le 1980

and contribute

\begin{aligned} \sum_{k=1}^{44} k \cdot 2k &= 2 \cdot \frac{44 \cdot 45 \cdot 89}{6} \\ &= 58740. \end{aligned}

The remaining

27

values

p = 1981, \ldots, 2007

each have

b(p) = 45,

adding

27 \cdot 45 = 1215.

Thus

S = 58740 + 1215 = 59955,

and the remainder is

955.