Question

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

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 $\sum_{k=1}^{44} k \cdot 2k = 2 \cdot \frac{44 \cdot 45 \cdot 89}{6} = 58740.$ 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.$

2007 AIME I Problem 11

Solution:

Problem 11 in Other Years