2003 AMC 10B Problem 7

P1-10~2 minPrint

Number Properties Sequences & Series Organized listing / direct enumeration Compute small cases, spot the pattern, generalize

The symbolism $\lfloor x \rfloor$ denotes the largest integer not exceeding $x$ . For example, $\lfloor 3 \rfloor = 3,$ and $\lfloor 9/2 \rfloor = 4$ . Compute $\lfloor \sqrt{1} \rfloor + \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor + \cdots + \lfloor \sqrt{16} \rfloor.$

Show solution without answering

Key insight

The rounded-down square root stays the same between perfect squares: it is 1 three times, 2 five times, 3 seven times, then 4 once at 16.

Solution

$\lfloor \sqrt{n} \rfloor$ means: take the square root, then drop anything after the decimal point. It only changes value when $n$ passes a perfect square, so split $1$ to $16$ at the perfect squares $1, 4, 9, 16$ .
Make a table:

$n$	$\sqrt{n}$ is between	$\lfloor \sqrt{n} \rfloor$	How many $n$
$1, 2, 3$	$1$ and $2$	$1$	$3$
$4, 5, 6, 7, 8$	$2$ and $3$	$2$	$5$
$9, 10, \ldots, 15$	$3$ and $4$	$3$	$7$
$16$	exactly $4$	$4$	$1$

3. Add each value times how many times it appears:
$3 \cdot 1 + 5 \cdot 2 + 7 \cdot 3 + 1 \cdot 4 = 3 + 10 + 21 + 4 = 38.$

The answer is $\boxed{\textbf{(B)}\ 38}$ .

Why this works

Between two perfect squares the rounded-down root does not change, so sixteen separate values collapse into four groups. The group for value $k$ runs from $k^2$ up to just before $(k+1)^2$ , which is $2k + 1$ numbers: $3, 5, 7, \ldots$ . When a sum has many equal terms, group them and multiply.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

$\lfloor \sqrt{n} \rfloor = k$ exactly when $k^2 \le n < (k+1)^2$ . Split $1$ through $16$ by the perfect squares $1, 4, 9, 16$ :

$n = 1, 2, 3$ : three terms, each equal to $1$ ;
$n = 4, \dots, 8$ : five terms, each equal to $2$ ;
$n = 9, \dots, 15$ : seven terms, each equal to $3$ ;
$n = 16$ : one term equal to $4$ .

Adding,
$3 \cdot 1 + 5 \cdot 2 + 7 \cdot 3 + 1 \cdot 4 = 3 + 10 + 21 + 4 = 38.$

The answer is $\boxed{\textbf{(B)}\ 38}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics
Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.2)
Introduction to Algebra, Chapter 20: Special Functions (§20.3)