2006 AIME II Problem 14

Attempt Problem 14 of the 2006 AIME II below, then check your answer against the professionally curated solution 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 problems are used with official legal permission of the Mathematical Association of America (MAA).

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.

Answer: 63
Concepts:digitsdivisibilitysummation
Difficulty rating: 3060
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. \begin{aligned} S_n &= 1 \\ &\quad {}+ n \\ &\quad {}\cdot 10^{n-1}\small\left(1 + \frac{1}{2} + \cdots + \frac{1}{9}\right) \\ &= 1 + \frac{7129}{2520}\, n \cdot 10^{n-1}. \end{aligned}

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 13#13
Full Exam

Problem 14 in Other Years