Competition problem — Algebra — Maths Olympiad Prep

Algebra Difficulty 5.5 AIME, harder Prove it Italy

Problem:

If $x$ is a positive real number, let $[x]$ denote the integer part of $x$ , that is the greatest integer $n \leq x$ . Compute the sum $\sum_{n=1}^{1000000} [\sqrt{n}] = [\sqrt{1}] + [\sqrt{2}] + \ldots + [\sqrt{999999}] + [\sqrt{1000000}]$ .

[The student may use, if they wish, the following formula: $\sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}$ , whose proof is not required.]

Solution

Solution:

We have $[\sqrt{n}] = k$ if and only if $k^2 \leq n < (k+1)^2 = k^2 + 2k + 1$ , that is for $n = k^2 + j$ with $0 \leq j \leq 2k$ , that is for $2k + 1$ values of $j$ .

Therefore,
$\begin{gathered} \sum_{n=1}^{K^2-1} [\sqrt{n}] = \sum_{k=1}^{K-1} k(2k+1) = \\ = 2 \sum_{k=1}^{K-1} k^2 + \sum_{k=1}^{K-1} k = \frac{(K-1)K(2K-1)}{3} + \frac{K(K-1)}{2} = \frac{(K-1)K(4K+1)}{6} \end{gathered}$

The required sum is obtained from expression $(*)$ by setting $K = 1000$ and adding $1000 = \sqrt{1000000}$ , which had not yet been counted: thus we obtain $500 \cdot (333 \cdot 4001 + 2)$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.