AIME 2006 II · 第 14 题

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 $\boxed{063}$.

Solution 2 (easier approach but nearly same logic)

Consider $n \ge 2$, since clearly $n = 1$ doesn't work.

For a certain $1/i$ to be summed such that it is an integer, we must have $i$ to be summed continuously $mi$ times for some integer $m$. For example, if we have $1/5$, we sum $1/5$ either $5, 10, 15, \dots$ times to obtain an integer.

Thus, every digit $i$ must be $1, 2, 3, \dots, 9$. It is known that every digit between every period $10^k$ appears the same number of times. For example, for the first $100$ numbers (excluding $0$ and $100$), every digit from $1 \text{--} 9$ appears the same number of times.

If we can find an algorithm that calculates the number of times a digit appears between $1$ and $10^n$, and extend that for all values of $n$, we could look for a specific value of $n$ such that every digit $1, 2, 3, \dots, 9$ appears a number of times such that all the reciprocals, when summed, are integers.

To find this algorithm, we construct a pattern. Consider $1 \text{--} 100$. Let's try to find the number of $9$'s between this interval. There are $9$ numbers (excluding from $90 \text{--} 99$), whose units digits is $9$. From $90 \text{--} 98$, we have nine $9$'s. $99$ gives us $2$ more $9$'s, and thus we have a total of $11 + 9 = 20$ nines. We then consider $1 \text{--} 1000$. Between $1$ and $100$, we have $21$ nines. The same applies from $101 \text{--} 200, 201 \text{--} 300, \dots, 801 \text{--} 899$. We then have a total of $21 \times 9 = 189$ nines. Then, we have $1$ nine from $900$, so $190$ nines. Then, from $901 \text{--} 908, 911 \text{--} 918, 921 \text{--} 928, \dots, 981 \text{--} 988$, we have one $9$, contributing $8 \times 9 = 72$ nines. For $10$ additional numbers ($909, 919, 929, \dots, 989, 990$), we have $2$ nines, contributing $20$ nines. Then, for the final set of $9$, we also have $2$ nines each, giving $18$ more nines, and the last $999$ has $3$ nines, giving a total of $190 + 72 + 20 + 18 = 300$ nines.

Now we must find a pattern. For every number $1 \text{--} 10^n$, we must find the number of $9$'s. Note that for all numbers less than $10^n$, we are given that $9$ can appear in any one of the positions between the units digit, and the $10^n$ decimal digit. That is $n$ places. For each $10^n$ places, the numbers appear equally often, and thus there are $10^n / 10 = 10^{n-1}$ slots. Our algorithm is then $n \cdot 10^{n-1}$.

Note that this formula also works for $2, 3, 4, \dots, 8$. For $1$, note that we have to add $1$ that appears from $10^n$, so the formula for $1$ is slightly different, being $n \cdot 10^{n-1} + 1$.

Thus, we now are at the second part. We require $n$ such that

$$1 \mid (n \cdot 10^{n-1} + 1) \quad \text{and} \quad 2, 3, 4, 5, \dots, 9 \mid n \cdot 10^{n-1}$$ Obviously, the former is always true, as $1$ divides everything. Thus, we neglect the former and pay attention to the latter.

The $\text{lcm}(2,3,4,5,\dots,9)$, after some work, is 2520. Thus, $2520 \mid n \cdot 10^{n-1}$. The prime factorization of 2520 is $2^3 \cdot 3^2 \cdot 5 \cdot 7$. The prime factorization of $10^{n-1}$ is $2^{n-1} \cdot 5^{n-1}$. To check extraneous, note that for $n \ge 4$, we have that $2^{n-1} \ge 2^3$, and the same for $5^{n-1}$ with $n \ge 2$, hence this is solvable. Because 9 and 7 are not factors of 10, we have that 9 and 7 must divide into $n$, meaning that $63 \mid n$. The smallest $n$ is then right in front of us, or $\boxed{063}$.

~Pinotation