HMMT 二月 2013 · 代数 · 第 10 题

10. Let N be a positive integer whose decimal representation contains 11235 as a contiguous substring, k and let k be a positive integer such that 10 > N . Find the minimum possible value of Algebra Test k 10 − 1 . k gcd( N, 10 − 1) k 10 − 1 N a Answer: 89 Set m = . Then, in lowest terms, = for some integer a . On the k k gcd( N, 10 − 1) 10 − 1 m N other hand, the decimal expansion of simply consists of the decimal expansion of N , possibly k 10 − 1 with some padded zeros, repeating. Since N contains 11235 as a contiguous substring, the decimal a representation of must as well. m Conversely, if m is relatively prime to 10 and if there exists an a such that the decimal representation k a 10 − 1 of contains the substring 11235, we claim that m is an attainable value for . To see k m gcd( N, 10 − 1) k this, note that since m is relatively prime to 10, there exists a value of k such that m divides 10 − 1 k a as N (for example, k = φ ( m )). Letting ms = 10 − 1 and N = as , it follows that = = . Since k m ms 10 − 1 the decimal expansion of this fraction contains the substring 11235, it follows that N must also, and therefore m is an attainable value. a We are therefore looking for a fraction which contains the substring 11235 in its decimal expansion. m Since 1, 1, 2, 3, and 5 are the first five Fibonacci numbers, it makes sense to look at the value of the infinite series ∞ ∑ F i . i 10 i =1 ∑ ∞ x i A simple generating function argument shows that F x = , so substituting x = 1 / 10 i 2 i =1 1 − x − x leads us to the fraction 10 / 89 (which indeed begins 0 . 11235 . . . ). ′ ′ How do we know no smaller values of m are possible? Well, if a /m contains the substring 11235 somewhere in its infinitely repeating decimal expansion, then note that there is an i such that the i ′ ′ decimal expansion of the fractional part of 10 ( a /m ) begins with 0 . 11235 . . . . We can therefore, ′ ′ without loss of generality, assume that the decimal representation of a /m begins 0 . 11235 . . . . But since the decimal representation of 10 / 89 begins 0 . 11235 . . . , it follows that ∣ ∣ ′ ∣ ∣ 10 a − 5 ∣ ∣ − ≤ 10 . ∣ ∣ ′ 89 m 1 ′ On the other hand, this absolute difference, if non-zero, is at least . If m < 89, this is at least ′ 89 m 1 − 5 ′

10 , and therefore no smaller values of m are possible. 2 89 Algebra Test