Difference between revisions of "2010 AIME I Problems/Problem 14"
(→Solution) |
Martin13579 (talk | contribs) m (→Video Solution: video does work anymore) |
||
(8 intermediate revisions by 7 users not shown) | |||
Line 1: | Line 1: | ||
__TOC__ | __TOC__ | ||
== Problem == | == 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>. | '''Note:''' <math>\lfloor x \rfloor</math> is the greatest integer less than or equal to <math>x</math>. | ||
− | + | == Solution 1 == | |
− | |||
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. | 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 == | |
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 == | |
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> | 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> | ||
Line 20: | Line 19: | ||
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>. | 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>. | ||
− | + | == 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. | 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. |
Latest revision as of 00:06, 19 October 2024
Contents
[hide]Problem
For each positive integer , let . Find the largest value of for which .
Note: is the greatest integer less than or equal to .
Solution 1
Observe that is strictly increasing in . We realize that we need terms to add up to around , so we need some sequence of s, s, and then s.
It follows that (alternatively, use binary search to get to this, with ). Manually checking shows that and . Thus, our answer is .
Solution 2
Because we want the value for which , the average value of the 100 terms of the sequence should be around . For the value of to be , . We want kn to be around the middle of that range, and for k to be in the middle of 0 and 100, let , so , and . , so we want to lower . Testing yields , so our answer is still .
Solution 3
For any where the sum is close to , all the terms in the sum must be equal to , or . Let be the number of terms less than or equal to and be the number of terms equal to (also counted in ). With this definition of and the total will be , from which . Now is the smallest integer for which or , thus Similarly,
Therefore, Since we want the largest possible , the answer is .
Solution 4 (similar to Solution 1, but with more detail)
Since we're working with base- logarithms, we can start by testing out 's that are powers of . For , the terms in the sum are . For numbers -, . Then we have numbers, namely -, for which . The last number we have is , which gives us . This sum gives us only , which is much too low. However, applying the same counting technique for , our sum comes out to be , since there are terms for which , terms for which , and one term for which . So we go up one more power of and get , which is very close to what we are looking for.
Now we only have to bump up the value of a bit and check our sum. Each increase in by actually increases the value of our sum by as well (except for ), because whenever a is added to the sum, a is taken away. It doesn't take long to check and see that the value of we're looking for is , which corresponds to a sum of exactly .
~ anellipticcurveoverq
See Also
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.