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

Latest revision as of 00:06, 19 October 2024

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$ (alternatively, use binary search to get to this, with $n\le 1000$ ). 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 \le 300$ , from which $M + N \ge 100$ . Now $M+1$ is the smallest integer $k$ for which $\log_{10}(kn) \ge 4$ or $kn \ge 10000$ , thus $M = \left\lfloor\frac{9999}{n}\right\rfloor.$ Similarly, $N = \left\lfloor\frac{999}{n}\right\rfloor = \left\lfloor\frac{M}{10}\right\rfloor.$

Therefore, $M + \left\lfloor \frac{M}{10} \right\rfloor \ge 100 \implies M \ge \left\lceil\frac{1000}{11}\right\rceil = 91 \implies n \le \left\lfloor\frac{9999}{91}\right\rfloor = 109.$ Since we want the largest possible $n$ , the answer is $\boxed{109}$ .

Solution 4 (similar to Solution 1, but with more detail)

Since we're working with base- $10$ logarithms, we can start by testing out $n$ 's that are powers of $10$ . For $n = 1$ , the terms in the sum are $\lfloor \log_{10} (1)\rfloor, \lfloor \log_{10} (2)\rfloor, \lfloor \log_{10} (3) \rfloor , . . . , \lfloor \log_{10} (100) \rfloor$ . For numbers $1$ - $9$ , $\lfloor \log_{10} (kn) \rfloor = 0$ . Then we have $90$ numbers, namely $10$ - $99$ , for which $\lfloor \log_{10} (kn) \rfloor = 1$ . The last number we have is $100$ , which gives us $\lfloor \log_{10} (kn) \rfloor = 2$ . This sum gives us only $90 + 2 = 92$ , which is much too low. However, applying the same counting technique for $n = 10$ , our sum comes out to be $9 + 180 + 3 = 192$ , since there are $9$ terms for which $\lfloor \log_{10} (kn) \rfloor = 1$ , $90$ terms for which $\lfloor \log_{10} (kn) \rfloor = 2$ , and one term for which $\lfloor \log_{10} (kn) \rfloor = 3$ . So we go up one more power of $10$ and get $18 + 270 + 4 = 292$ , which is very close to what we are looking for.

Now we only have to bump up the value of $n$ a bit and check our sum. Each increase in $n$ by $1$ actually increases the value of our sum by $1$ as well (except for $n = 101$ ), because whenever a $4$ is added to the sum, a $3$ is taken away. It doesn't take long to check and see that the value of $n$ we're looking for is $\boxed{109}$ , which corresponds to a sum of exactly $300$ .

~ anellipticcurveoverq

@@ Line 1: / Line 1: @@
+__TOC__
 == Problem ==
-For each positive integer n, let <math>f(n) = \sum_{k = 1}^{100} \lfloor \log_{10} (kn) \rfloor</math>. Find the largest value of n for which <math>f(n) \le 300</math>.
+For each positive integer <math>n</math>, let <math>f(n) = \sum_{k = 1}^{100} \lfloor \log_{10} (kn) \rfloor</math>. Find the largest value of <math>n</math> for which <math>f(n) \le 300</math>.
 '''Note:''' <math>\lfloor x \rfloor</math> is the greatest integer less than or equal to <math>x</math>.
@@ Line 7: / Line 8: @@
 Observe that <math>f</math> is strictly increasing in <math>n</math>. We realize that we need <math>100</math> terms to add up to around <math>300</math>, so we need some sequence of <math>2</math>s, <math>3</math>s, and then <math>4</math>s.
-It follows that <math>n \approx 100</math>. Manually checking shows that <math>f(109) = 300</math> and <math>f(110) > 300</math>. Thus, our answer is <math>\boxed{109}</math>.
+It follows that <math>n \approx 100</math> (alternatively, use binary search to get to this, with <math>n\le 1000</math>). Manually checking shows that <math>f(109) = 300</math> and <math>f(110) > 300</math>. Thus, our answer is <math>\boxed{109}</math>.
 == Solution 2 ==
@@ Line 14: / Line 15: @@
 == Solution 3 ==
-For any <math>n</math> where the sum is close to <math>300</math>, all the terms in the sum must be equal to <math>2</math>, <math>3</math> or <math>4</math>. Let <math>M</math> be the number of terms less than or equal to <math>3</math> and <math>N</math> be the number of terms equal to <math>2</math> (also counted in <math>M</math>). With this definition of <math>M</math> and <math>N</math> the total will be <math>400 - M - N = 300</math>, from which <math>M + N = 100</math>. Now <math>M+1</math> is the smallest integer <math>k</math> for which <math>\log_{10}(kn) \ge 4</math> or <math>kn \ge 10000</math>, thus <cmath>M = \left\lceil\frac{10000}{n}\right\rceil - 1.</cmath> Similarly, <cmath>N = \left\lceil\frac{1000}{n}\right\rceil - 1.</cmath>
+For any <math>n</math> where the sum is close to <math>300</math>, all the terms in the sum must be equal to <math>2</math>, <math>3</math> or <math>4</math>. Let <math>M</math> be the number of terms less than or equal to <math>3</math> and <math>N</math> be the number of terms equal to <math>2</math> (also counted in <math>M</math>). With this definition of <math>M</math> and <math>N</math> the total will be <math>400 - M - N \le 300</math>, from which <math>M + N \ge 100</math>. Now <math>M+1</math> is the smallest integer <math>k</math> for which <math>\log_{10}(kn) \ge 4</math> or <math>kn \ge 10000</math>, thus <cmath>M = \left\lfloor\frac{9999}{n}\right\rfloor.</cmath> Similarly, <cmath>N = \left\lfloor\frac{999}{n}\right\rfloor = \left\lfloor\frac{M}{10}\right\rfloor.</cmath>
-If <math>n</math> is not a divisor of <math>10000</math>, we have <cmath>M = \left\lfloor\frac{10000}{n}\right\rfloor</cmath> and <cmath>N = \left\lfloor\frac{1000}{n}\right\rfloor = \left\lfloor \frac{M}{10} \right\rfloor.</cmath> Under the same assumption, <cmath>M + \left\lfloor \frac{M}{10} \right\rfloor = 100,</cmath> and so <math>M = 91</math>. Dividing <math>10000</math> by <math>91</math> we see that <math>n = 109</math>. Since <math>n = 110</math> is also not a divisor of <math>10000</math> and with <math>n = 110</math> we get <math>M + N = 90 + 9 = 99 < 100</math> (thus a sum of <math>301 > 300</math>) and the sum is obviously monotone in <math>n</math>, the largest value is <math>\boxed{109}</math>.
+Therefore, <cmath>M + \left\lfloor \frac{M}{10} \right\rfloor \ge 100 \implies M \ge \left\lceil\frac{1000}{11}\right\rceil = 91 \implies n \le \left\lfloor\frac{9999}{91}\right\rfloor = 109.</cmath> Since we want the largest possible <math>n</math>, the answer is  <math>\boxed{109}</math>.
-== See also ==
+== Solution 4 (similar to Solution 1, but with more detail) ==
+Since we're working with base-<math>10</math> logarithms, we can start by testing out <math>n</math>'s that are powers of <math>10</math>. For <math>n = 1</math>, the terms in the sum are <math>\lfloor \log_{10} (1)\rfloor, \lfloor \log_{10} (2)\rfloor, \lfloor \log_{10} (3) \rfloor , . . . , \lfloor \log_{10} (100) \rfloor</math>. For numbers <math>1</math>-<math>9</math>, <math>\lfloor \log_{10} (kn) \rfloor = 0</math>. Then we have <math>90</math> numbers, namely <math>10</math>-<math>99</math>, for which <math>\lfloor \log_{10} (kn) \rfloor = 1</math>. The last number we have is <math>100</math>, which gives us <math>\lfloor \log_{10} (kn) \rfloor = 2</math>. This sum gives us only <math>90 + 2 = 92</math>, which is much too low. However, applying the same counting technique for <math>n = 10</math>, our sum comes out to be <math>9 + 180 + 3 = 192</math>, since there are <math>9</math> terms for which <math>\lfloor \log_{10} (kn) \rfloor = 1</math>, <math>90</math> terms for which <math>\lfloor \log_{10} (kn) \rfloor = 2</math>, and one term for which <math>\lfloor \log_{10} (kn) \rfloor = 3</math>. So we go up one more power of <math>10</math> and get <math>18 + 270 + 4 = 292</math>, which is very close to what we are looking for.
+Now we only have to bump up the value of <math>n</math> a bit and check our sum. Each increase in <math>n</math> by <math>1</math> actually increases the value of our sum by <math>1</math> as well (except for <math>n = 101</math>), because whenever a <math>4</math> is added to the sum, a <math>3</math> is taken away. It doesn't take long to check and see that the value of <math>n</math> we're looking for is <math>\boxed{109}</math> , which corresponds to a sum of exactly <math>300</math>.
+~ anellipticcurveoverq
+== See Also ==
 {{AIME box|year=2010|num-b=13|num-a=15|n=I}}
 [[Category:Intermediate Algebra Problems]]
+{{MAA Notice}}

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