How to evaluate a sum of square roots rounded to the nearest integer?

Question

This is (adapted from) Problem 11 from the 2007 AIME :

For each positive integer $p$, let $b(p)$ denote the unique positive integer $k$ such that $|k-\sqrt{p}|<\frac{1}{2}$. For example, $b(6)=2$ and $b(23)=5$. Find $S=\sum_{p=1}^{2007} b(p)$.

I started by noting that $$\left(k- \frac 12\right)^2=k^2-k+\frac 14\text{ and }\left(k+ \frac 12\right)^2=k^2+k+ \frac 14.$$

So, all numbers from $1-44$ will have the maximum value in the range.

How should I continue, or approach the problem.

Answer 1

As you notice, for positive integers $p$ and $k$, $b(p)=k$ if and only if $k-\dfrac12< \sqrt{p} < k+\dfrac12$, which is equivalent to $$(k-1)^2+(k-1)=k^2-k<p\leq k^2+k\,.$$ Now, $44\cdot 45=1980<2007<2070=45\cdot 46$, we see that $b(P)=K$ with $P:=2007$ and $K:=45$.

Rewrite the required sum $S:=\sum\limits_{p=1}^P\,b(p)$ as $$S=\sum_{k=1}^{K-1}\,k\,n(k)+K\,\Big(P-\big(K^2-K\big)\Big)\,,$$ where, for each $k=1,2,3,\ldots$, $n(k):=(k^2+k)-(k^2-k)=2k$ is the number of positive integers $p$ such that $b(p)=k$. (Note that $P-\big(K^2-K\big)$ is the number of positive integers $p\leq P$ such that $b(p)=K$.) Hence, $$S=\sum_{k=1}^{K-1}\,k\cdot(2k)+K\,\Big(P-\big(K^2-K\big)\Big)=2\left(\frac{K(K-1)(2K-1)}{6}\right)+KP-K^2(K-1)\,.$$ Hence, $$S=KP-\frac{(K-1)K\big(3K-(2K-1)\big)}{3}=KP-\frac{(K-1)K(K+1)}{3}\,.$$ With $K=45$ and $P=2007$, we get $$S=45\cdot 2007-\frac{44\cdot 45\cdot 46}{6}=90315-30360=59955\,.$$ For a general value of positive integer $P$, $$S=\frac13\left\lceil\sqrt{P+\frac14}-\frac12\right\rceil\left(3P-\left\lceil\sqrt{P+\frac14}-\frac12\right\rceil^2+1\right)\,.$$

Answer 2

If you try out a few numbers, you start to see the pattern, namely $$11222233333344444444....$$ Each number $n$ appears $2n$ times. That is, $n$ appears between $n^2 - n + 1$ and $n^2 + n$ inclusive. It ends when $n = 45$, which corresponds to the range $45^2 - 45 + 1 = 1981$ to $45^2 + 45 = 2070$, but since you cut off at $p = 2007$ you only include $45$ a total of $27$ times. So your sum is $$\sum_{n = 1}^{44} 2n^2 + 45*27$$ Using the formula $\sum_{n=1}^k n^2 = {k(k+1)(2k+1) \over 6}$, we get $$\sum_{n = 1}^{44} 2n^2 + 45*27 = {44*45*89 \over 3} + 45*27$$ $$= 58740 + 1215$$ $$= 59955$$ Not sure how a high school kid is supposed to do it on a timed exam, but this is pretty elementary at least.