AIME 1994 · 第 4 题

Solution 1

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, 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\cdot2^j) + k(n-2^k+1) = 1994$.

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

Alternatively, one could notice this is an arithmetico-geometric series and avoid a lot of computation.

Solution 2

For this solution, we notice that values between ranges of $2^n$ are the same. Let's look at these ranges and their total value. It is trivial to conclude $\log_2{1} = 0$ so we will not write that.

\begin{array}{c|c} \text{Range of } k & \text{Expression (Total)} \\ \hline 2 \leq k < 2^2 & 1 \cdot (2^2 - 2) = 2 \\ 2^2 \leq k < 2^3 & 2 \cdot (2^3 - 2^2) = 8 \\ 2^3 \leq k < 2^4 & 3 \cdot (2^4 - 2^3) = 24 \\ 2^4 \leq k < 2^5 & 4 \cdot (2^5 - 2^4) = 64 \\ 2^5 \leq k < 2^6 & 5 \cdot (2^6 - 2^5) = 160 \\ 2^6 \leq k < 2^7 & 6 \cdot (2^7 - 2^6) = 384 \\ 2^7 \leq k < 2^8 & 7 \cdot (2^8 - 2^7) = 896 \\ \end{array}

Sum of the values up to $1$ less than $2^k$ is $1538$. This seems close enough to our desired value of $1994$ as any additional groups would exceed $1994$. The difference is $1996 - 1538 = 456$. Since the next numbers of the sequence will always be 8 since $\lfloor \log_2{2^8 + n < 2^9} \rfloor = 8$, we can just find the number of '8's, which is $\frac{456}{8} = 57$. So there are exactly 57 integers in that range. The largest integer, which is $a$, is equal to $2^8 + 56 = \boxed{312}$. ~Totient4Breakfast

Solution 3 (Variation of Solution 1)

Like in solution 1, continue upon realization that we get the series $0 + 2(1) + 4(2) + 8(3) + \dots + k(n)$.

Then, this series can be written as

$$\sum_{k=0}^n k2^k = 1994$$ Continuing forth with solution 1, we can see that if $n=7$, we get $1538 < 1994$, and if $n=8$, we get $3586 > 1994$.

Then, we see that there must be $m(8)$ such that $1538 + 8m = 1994$. Solving for $m$ we get $m=57$.

We see that $2^k + 2^{k+1} + 2^{k+2} + \dots + 2^{k+n}$ is the number of terms in this sequence for $0 \le k \le 7$ and $n=7$, and we include the additional 57 terms. To do this, we don't want to include the arithmetic portion of our series, turning our arithmetico-geometric series into

$$\left(\sum_{k=0}^n 2^k\right) + 57$$ The finite geometric sum results in 255, in which the value of $n$ is determined as $255 + 57 =$ $\boxed{312}$.

~Pinotation