2006 AIME II Problem 14

Below is the professionally curated solution for Problem 14 of the 2006 AIME II, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2006 AIME II solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:digitsdivisibilitysummation

Difficulty rating: 3060

14.

Let SnS_n be the sum of the reciprocals of the nonzero digits of the integers from 11 to 10n,10^n, inclusive. Find the smallest positive integer nn for which SnS_n is an integer.

Solution:

Write the integers from 00 to 10n110^n - 1 as nn-digit strings with leading zeros. Each of the nn digit positions takes each digit value equally often, so each nonzero digit appears n10n1n \cdot 10^{n-1} times. Adding the digit 11 of 10n10^n itself, Sn=1+n10n1(1+12++19)=1+71292520n10n1.S_n = 1 + n \cdot 10^{n-1}\left(1 + \frac{1}{2} + \cdots + \frac{1}{9}\right) = 1 + \frac{7129}{2520}\, n \cdot 10^{n-1}.

Since gcd(7129,2520)=1,\gcd(7129, 2520) = 1, the sum is an integer exactly when 2520n10n1.2520 \mid n \cdot 10^{n-1}. Now 2520=233257,2520 = 2^3 \cdot 3^2 \cdot 5 \cdot 7, and for n4n \ge 4 the factor 10n110^{n-1} supplies 235,2^3 \cdot 5, leaving the condition 63n63 \mid n (a power of 1010 has no factors of 33 or 77). For n=1,2,3n = 1, 2, 3 the products 1,20,3001, 20, 300 are not multiples of 2520.2520.

The smallest solution is therefore n=63.n = 63.

← Problem 13Full ExamProblem 15

Problem 14 in Other Years