Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1986 AHSME Problems/Problem 25"

(→‎Solution)
m (→‎Solution)
Line 16: Line 16:
 
For all <math>k</math> except for <math>k=10</math>, we have that <math>\lfloor \log_{2}N\rfloor = k</math> is satisfied by all <math>2^k \le N<2^{k+1}</math>, for a total of <math>2^k</math> values of <math>N</math>. If <math>k=10</math>, <math>N</math> can only have one value (<math>N=1024</math>). Thus, the desired sum looks like <cmath>\sum_{N=1}^{1024} \lfloor \log_{2}N\rfloor =1(0)+2(1)+4(2)+\dots+2^k(k)+\dots+2^{9}(9)+10</cmath>
 
For all <math>k</math> except for <math>k=10</math>, we have that <math>\lfloor \log_{2}N\rfloor = k</math> is satisfied by all <math>2^k \le N<2^{k+1}</math>, for a total of <math>2^k</math> values of <math>N</math>. If <math>k=10</math>, <math>N</math> can only have one value (<math>N=1024</math>). Thus, the desired sum looks like <cmath>\sum_{N=1}^{1024} \lfloor \log_{2}N\rfloor =1(0)+2(1)+4(2)+\dots+2^k(k)+\dots+2^{9}(9)+10</cmath>
  
−
We ignore the <math>10</math> for now. Let <math>S=1(0)+2(1)+4(2)+\dots+2^{9}(9)</math>. We sum this geometric-arithmetic sequence in the following way:  
+
We ignore the <math>10</math> for now. Let <math>S=2(1)+4(2)+\dots+2^{9}(9)</math>. We sum this geometric-arithmetic sequence in the following way:  
  
−
<cmath>S=1(0)+2(1)+4(2)+\dots+2^{9}(9)</cmath> Multiplying by <math>2</math> gives <cmath>2S=2(0)+4(1)+8(2)+\dots+2^{10}(9)</cmath> Subtracting the two equations gives <cmath>S=2^{10}(9)-(2+4+8+\dots+2^9)</cmath> Summing the geometric sequence and simplifying, we get <cmath>S=2^{10}(9)-2^{10}+2=2^{10}(8)+2=8194</cmath> Finally, adding back the <math>10</math> gives the desired answer <math>\fbox{(B) 8204}</math>
+
<cmath>S=2(1)+4(2)+\dots+2^{9}(9)</cmath> Multiplying by <math>2</math> gives <cmath>2S=4(1)+8(2)+\dots+2^{10}(9)</cmath> Subtracting the two equations gives <cmath>S=2^{10}(9)-(2+4+8+\dots+2^9)</cmath> Summing the geometric sequence and simplifying, we get <cmath>S=2^{10}(9)-2^{10}+2=2^{10}(8)+2=8194</cmath> Finally, adding back the <math>10</math> gives the desired answer <math>\fbox{(B) 8204}</math>
  
 
== See also ==
 
== See also ==

Revision as of 16:10, 2 August 2016

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}$

See also

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1986_AHSME_Problems/Problem_25&oldid=79818"