Difference between revisions of "1994 AIME Problems/Problem 4"
I like pie (talk | contribs) (Started solution) |
|||
Line 7: | Line 7: | ||
== Solution == | == Solution == | ||
− | + | Note that if <math>2^x \le a<2^{x+1}</math> for some <math>x\in\mathbb{Z}</math>, then <math>\lfloor\log_2{a}\rfloor=\log_2{2^{x}}=x</math>. | |
− | |||
− | \log_2{ | ||
− | </ | ||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | Thus, there are <math>2^{x+1}-2^{x}=2^{x}</math> integers <math>a</math> such that <math>\lfloor\log_2{a}\rfloor=x</math>. So the sum of <math>\lfloor\log_2{a}\rfloor</math> for all such <math>a</math> is <math>x\cdot2^x</math>. | ||
+ | |||
+ | Let <math>k</math> be the integer such that <math>2^k \le n<2^{k+1}</math>. So for each integer <math>j<k</math>, there are <math>2^j</math> integers <math>a\le n</math> such that <math>\lfloor\log_2{a}\rfloor=j</math>, and there are <math>n-2^k+1</math> such integers such that <math>\lfloor\log_2{a}\rfloor=k</math>. | ||
+ | |||
+ | Therefore, <math>\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\cdot2^j) + k(n-2^k+1) = 1994</math>. | ||
+ | |||
+ | Through computation: <math>\sum_{j=0}^{7}(j\cdot2^j)=1538<1994</math> and <math>\sum_{j=0}^{8}(j\cdot2^j)=3586>1994</math>. Thus, <math>k=8</math>. | ||
+ | |||
+ | So, <math>\sum_{j=0}^{k-1}(j\cdot2^j) + k(n-2^k+1) = 1538+8(n-2^8+1)=1994 \Rightarrow n = \boxed{312}</math>. | ||
+ | |||
== See also == | == See also == | ||
{{AIME box|year=1994|num-b=3|num-a=5}} | {{AIME box|year=1994|num-b=3|num-a=5}} |
Revision as of 21:52, 22 July 2008
Problem
Find the positive integer for which
(For real
,
is the greatest integer
)
Solution
Note that if for some
, then
.
Thus, there are integers
such that
. So the sum of
for all such
is
.
Let be the integer such that
. So for each integer
, there are
integers
such that
, and there are
such integers such that
.
Therefore, .
Through computation: and
. Thus,
.
So, .
See also
1994 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |