Maths Olympiad Prep

Library / /413 of 520

Number theory Difficulty 3.7 AMC 10/12 Find the answer

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

Pick one

Solution

Because 1N10241 \le N \le 1024, we have 0log2N100 \le \lfloor \log_{2}N\rfloor \le 10. We count how many times log2N\lfloor \log_{2}N\rfloor attains a certain value.
For all kk except for k=10k=10, we have that log2N=k\lfloor \log_{2}N\rfloor = k is satisfied by all 2kN<2k+12^k \le N<2^{k+1}, for a total of 2k2^k values of NN. If k=10k=10, NN can only have one value (N=1024N=1024). Thus, the desired sum looks like N=11024log2N=1(0)+2(1)+4(2)++2k(k)++29(9)+10\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 SS be the desired sum without the 1010. S=2(1)+4(2)++29(9)S=2(1)+4(2)+\dots+2^{9}(9) Multiplying by 22 gives 2S=4(1)+8(2)++210(9)2S=4(1)+8(2)+\dots+2^{10}(9) Subtracting the two equations gives S=210(9)(2+4+8++29)S=2^{10}(9)-(2+4+8+\dots+2^9) Summing the geometric sequence in parentheses and simplifying, we get S=210(9)210+2=210(8)+2=8194S=2^{10}(9)-2^{10}+2=2^{10}(8)+2=8194 Finally, adding back the 1010 gives the desired answer (B) 8204\fbox{(B) 8204}

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.