AoPSWiki

Want to learn how to tackle those tough AMC/AIME/Olympiad counting and probability problems? Check out Art of Problem Solving's Intermediate Counting & Probability by David Patrick.

Personal tools

Search

Toolbox

1994 AIME Problems/Problem 4

From AoPSWiki

Revision as of 01:52, 23 July 2008 by Xantos C. Guin (Talk | contribs)

(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

Problem

Find the positive integer $n\,$ for which $\lfloor\log_2{1}\rfloor+\lfloor\log_2{2}\rfloor+\lfloor\log_2{3}\rfloor+\cdots+\lfloor\log_2{n}\rfloor=1994$ (For real $x\,$ , $\lfloor x\rfloor\,$ is the greatest integer $\le x.\,$ )

Solution

Note that if $2^x \le a<2^{x+1}$ for some $x\in\mathbb{Z}$ , then $\lfloor\log_2{a}\rfloor=\log_2{2^{x}}=x$ .

Thus, there are $2^{x+1}-2^{x}=2^{x}$ integers $a$ such that $\lfloor\log_2{a}\rfloor=x$ . So the sum of $\lfloor\log_2{a}\rfloor$ for all such $a$ is $x\cdot2^x$ .

Let $k$ be the integer such that $2^k \le n<2^{k+1}$ . So for each integer $j<k$ , there are $2^j$ integers $a\le n$ such that $\lfloor\log_2{a}\rfloor=j$ , and there are $n-2^k+1$ such integers such that $\lfloor\log_2{a}\rfloor=k$ .

Therefore, $\lfloor\log_2{1}\rfloor+\lfloor\log_2{2}\rfloor+\lfloor\log_2{3}\rfloor+\cdots+\lfloor\log_2{n}\rfloor= \sum_{j=0}^{k-1}(j\cd...$ .

Through computation: $\sum_{j=0}^{7}(j\cdot2^j)=1538<1994$ and $\sum_{j=0}^{8}(j\cdot2^j)=3586>1994$ . Thus, $k=8$ .

So, $\sum_{j=0}^{k-1}(j\cdot2^j) + k(n-2^k+1) = 1538+8(n-2^8+1)=1994 \Rightarrow n = \boxed{312}$ .

See also

1994 AIME (Problems • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/1994_AIME_Problems/Problem_4"

Looking for a challenging algebra text? Preparing for MATHCOUNTS or the AMC exams?
Check out Art of Problem Solving's Introduction to Algebra by Richard Rusczyk.

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us