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 19: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 (ProblemsAnswer KeyResources)
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