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 "2006 AIME II Problems/Problem 14"

 
m
Line 1: Line 1:
−
#REDIRECT [[2006 AIME A Problems/Problem 14]]
+
== Problem ==
 +
 
 +
Let <math> S_n </math> be the sum of the reciprocals of the non-zero digits of the integers from 1 to <math> 10^n </math> inclusive. Find the smallest positive integer n for which <math> S_n </math> is an integer.
 +
 
 +
== Solution ==
 +
Let <math>K = \sum_{i=1}^{9}{\frac{1}{i}}</math>.  Examining the terms in <math>S_1</math>, we see that <math>S_1 = K + 1</math> since each digit <math>n</math> appears once and 1 appears an extra time.  Now consider writing out <math>S_2</math>.  Each term of <math>K</math> will appear 10 times in the units place and 10 times in the tens place (plus one extra 1 will appear), so <math>S_2 = 20K + 1</math>.
 +
 
 +
In general, we will have that:
 +
 
 +
<math>S_n = (n10^{n-1})K + 1</math>
 +
 
 +
because each digit will appear <math>10^{n - 1}</math> times in each place in the numbers <math>1, 2, \ldots, 10^{n} - 1</math>, and there are <math>n</math> total places. 
 +
 
 +
The denominator of <math>K</math> is <math>D = 2^3\cdot 3^2\cdot 5\cdot 7</math>.  For <math>S_n</math> to be an integer, <math>n10^{n-1}</math> must be divisible by <math>D</math>.  Since <math>10^{n-1}</math> only contains the factors 2 and 5 (but will contain enough of them when <math>n \geq 3</math>), we must choose <math>n</math> to be [[divisible]] by <math>3^2\cdot 7</math>.  Since we're looking for the smallest such <math>n</math>, the answer is <math>063</math>
 +
 
 +
== See also ==
 +
{{AIME box|year=2006|n=II|num-b=13|num-a=15}}
 +
 
 +
[[Category:Intermediate Number Theory Problems]]

Revision as of 18:11, 25 September 2007

Problem

Let $S_n$ be the sum of the reciprocals of the non-zero digits of the integers from 1 to $10^n$ inclusive. Find the smallest positive integer n for which $S_n$ is an integer.

Solution

Let $K = \sum_{i=1}^{9}{\frac{1}{i}}$. Examining the terms in $S_1$, we see that $S_1 = K + 1$ since each digit $n$ appears once and 1 appears an extra time. Now consider writing out $S_2$. Each term of $K$ will appear 10 times in the units place and 10 times in the tens place (plus one extra 1 will appear), so $S_2 = 20K + 1$.

In general, we will have that:

$S_n = (n10^{n-1})K + 1$

because each digit will appear $10^{n - 1}$ times in each place in the numbers $1, 2, \ldots, 10^{n} - 1$, and there are $n$ total places.

The denominator of $K$ is $D = 2^3\cdot 3^2\cdot 5\cdot 7$. For $S_n$ to be an integer, $n10^{n-1}$ must be divisible by $D$. Since $10^{n-1}$ only contains the factors 2 and 5 (but will contain enough of them when $n \geq 3$), we must choose $n$ to be divisible by $3^2\cdot 7$. Since we're looking for the smallest such $n$, the answer is $063$

See also

2006 AIME II (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=2006_AIME_II_Problems/Problem_14&oldid=16983"