1986 AHSME Problems/Problem 25

Problem

If $\lfloor x\rfloor$ is the greatest integer less than or equal to $x$ , then $\sum_{N=1}^{1024} \lfloor \log_{2}N\rfloor =$

$\textbf{(A)}\ 8192\qquad \textbf{(B)}\ 8204\qquad \textbf{(C)}\ 9218\qquad \textbf{(D)}\ \lfloor\log_{2}(1024!)\rfloor\qquad \textbf{(E)}\ \text{none of these}$

Solution

Because $1 \le N \le 1024$ , we have $0 \le \lfloor \log_{2}N\rfloor \le 10$ . We count how many times $\lfloor \log_{2}N\rfloor$ attains a certain value.

For all $k$ except for $k=10$ , we have that $\lfloor \log_{2}N\rfloor = k$ is satisfied by all $2^k \le N<2^{k+1}$ , for a total of $2^k$ values of $N$ . If $k=10$ , $N$ can only have one value ( $N=1024$ ). Thus, the desired sum looks like $\sum_{N=1}^{1024} \lfloor \log_{2}N\rfloor =1(0)+2(1)+4(2)+\dots+2^k(k)+\dots+2^{9}(9)+10$

We ignore the $10$ for now. Let $S=2(1)+4(2)+\dots+2^{9}(9)$ . We sum this geometric-arithmetic sequence in the following way:

$S=2(1)+4(2)+\dots+2^{9}(9)$ Multiplying by $2$ gives $2S=4(1)+8(2)+\dots+2^{10}(9)$ Subtracting the two equations gives $S=2^{10}(9)-(2+4+8+\dots+2^9)$ Summing the geometric sequence and simplifying, we get $S=2^{10}(9)-2^{10}+2=2^{10}(8)+2=8194$ Finally, adding back the $10$ gives the desired answer $\fbox{(B) 8204}$

1986 AHSME (Problems • Answer Key • Resources)
Preceded by Problem 24	Followed by Problem 26
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30
All AHSME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

Page

Toolbox

Search

1986 AHSME Problems/Problem 25

Problem

Solution

See also