Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution 3)
(→‎Solution 3)
Line 14: Line 14:
 
== Solution 3 ==
 
== Solution 3 ==
  
−
The sum will contain some 4's, 3's and 2's. 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(kn) >= 4</math> or <math>kn >= 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>. Unless <math>n</math> is a divisor of <math>10000</math>, we have <math></math>M = \left\lfloor\frac{10000}{n}\right\rfloor<math> and <cmath>N = \left\lfloor\frac{1000}{n}\right\rfloor = \left\lfloor \frac{M}{10} \right\rfloor</cmath>. Under the same assumption </math>M + \left\lfloor \frac{M}{10} \right\rfloor = 100<math>, and so </math>M = 91<math>. Dividing </math>10000<math> by </math>91<math> we see that </math>n<math> is </math>109<math>. Since </math>n = 110<math> yields </math>M + N < 100<math>, and the sum is monotone in </math>n<math>, the largest value is </math>109$.
+
The sum will contain some 4's, 3's and 2's. 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(kn) >= 4</math> or <math>kn >= 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>. Unless <math>n</math> is 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 <math>M + \left\lfloor \frac{M}{10} \right\rfloor = 100</math>, and so <math>M = 91</math>. Dividing <math>10000</math> by <math>91</math> we see that <math>n</math> is <math>109</math>. Since <math>n = 110</math> yields <math>M + N < 100</math>, and the sum is monotone in <math>n</math>, the largest value is <math>109</math>.
  
 
== See also ==
 
== See also ==

Revision as of 18:12, 21 March 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

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 = \left\lceil\frac{10000}{n}\right\rceil - 1\]. Similarly, \[N = \left\lceil\frac{1000}{n}\right\rceil - 1\]. Unless $n$ is 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$ is $109$. Since $n = 110$ yields $M + N < 100$, and the sum is monotone in $n$, the largest value is $109$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_AIME_I_Problems/Problem_14&oldid=33977"