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

Revision as of 02:06, 20 April 2010

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

For any $n$ where the sum is close to $300$ , all the terms in the sum must be equal to $2$ , $3$ or $4$ . 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_{10}(kn) \ge 4$ or $kn \ge 10000$ , thus $M = \left\lceil\frac{10000}{n}\right\rceil - 1.$ Similarly, $N = \left\lceil\frac{1000}{n}\right\rceil - 1.$

If $n$ is not a divisor of $10000$ , we have $M = \left\lfloor\frac{10000}{n}\right\rfloor$ and $N = \left\lfloor\frac{1000}{n}\right\rfloor = \left\lfloor \frac{M}{10} \right\rfloor.$ Under the same assumption, $M + \left\lfloor \frac{M}{10} \right\rfloor = 100,$ and so $M = 91$ . Dividing $10000$ by $91$ we see that $n = 109$ . Since $n = 110$ is also not a divisor of $10000$ and with $n = 110$ we get $M + N = 90 + 9 = 99 < 100$ (thus a sum of $301 > 300$ ) and the sum is obviously monotone in $n$ , the largest value is $\boxed{109}$ .

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

2010 AIME I (Problems • Answer Key • Resources)
Preceded by Problem 13	Followed by Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search