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\]

Let $S$ be the desired sum without the $10$. \[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 in parentheses 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}$

See also

1986 AHSME (ProblemsAnswer KeyResources)
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. AMC logo.png