# Difference between revisions of "2010 AIME I Problems/Problem 14"

## Problem

For each positive integer n, let $f(n) = \sum_{k = 1}^{100} \lfloor log_{10} (kn) \rfloor$. Find the largest value of n for which $f(n) \le 300$.

Note: $\lfloor x \rfloor$ is the greatest integer less than or equal to $x$.

## Solution 1

Observe that $f$ is strictly increasing in $n$. We realize that we need $100$ terms to add up to around $300$, so we need some sequence of $2$s, $3$s, and then $4$s.

It follows that $n \approx 100$. Manually checking shows that $f(109) = 300$ and $f(110) > 300$. Thus, our answer is $\boxed{109}$.

## Solution 2

Because we want the value for which $f(n)=300$, the average value of the 100 terms of the sequence should be around $3$. For the value of $\lfloor log_{10} (kn) \rfloor$ to be $3$, $1000 \le kn < 10000$. We want kn to be around the middle of that range, and for k to be in the middle of 0 and 100, let $k=50$, so $50n=\frac{10000+1000}{2}=\frac{11000}{2}=5500$, and $n = 110$. $f(110) = 301$, so we want to lower $n$. Testing $109$ yields $300$, so our answer is still $\boxed{109}$.

## Solution 3

The sum will contain some 4's, 3's and 2's. Let $M$ be the number of terms less than or equal to $3$ and $N$ be the number of terms equal to $2$ (also counted in $M$). With this definition of $M$ and $N$ the total will be $400 - M - N = 300$, from which $M + N = 100$. Now $M+1$ is the smallest integer $k$ for which $log(kn) >= 4$ or $kn >= 10000$, thus $M = \lceil\frac{10000}{n}\rceil - 1$. Similarly $N = \lceil\frac{1000}{n}\rceil - 1$. Unless $n$ is a divisor of $10000$, we have $M = \lfloor\frac{10000}{n}\rfloor$ and $N = \lfloor\frac{1000}{n}\rfloor = \lfloor \frac{M}{10} \rfloor$. Under the same assumption $M + \lfloor \frac{M}{10} \rfloor = 100$, and so $M = 91$. Dividing $10000$ by $91$ we see that $n$ is $109$. Since $n = 110$ yields $M + N < 100$, and the sum is monotone in $n$, the largest value is $109$.