HMMT 二月 2013 · 代数 · 第 10 题

英文解析

10. Let N be a positive integer whose decimal representation contains 11235 as a contiguous substring,
    and let k be a positive integer such that 10 > N . Find the minimum possible value ofk
    Algebra Testk
    10 − 1
    .
    gcd( N, 10 − 1)kk
    10 − 1 N a
    Answer: 89 Set m = . Then, in lowest terms, = for some integer a . On thek kgcd( N, 10 − 1) 10 − 1 mother hand, the decimal expansion of simply consists of the decimal expansion of N , possibly nk
    10 − 1
    with some padded zeros, repeating. Since N contains 11235 as a contiguous substring, the decimalarepresentation of must as well.
    Conversely, if m is relatively prime to 10 and if there exists an a such that the decimal representationmka 10 − 1
    of contains the substring 11235, we claim that m is an attainable value for . To seekm gcd( N, 10 − 1)
    this, note that since m is relatively prime to 10, there exists a value of k such that m divides 10 − 1 kk a as N
    (for example, k = φ ( m )). Letting ms = 10 − 1 and N = as , it follows that = = . Sincekm ms 10 − 1
    the decimal expansion of this fraction contains the substring 11235, it follows that N must also, andtherefore m is an attainable value.
    We are therefore looking for a fraction which contains the substring 11235 in its decimal expansion.am
    Since 1, 1, 2, 3, and 5 are the first five Fibonacci numbers, it makes sense to look at the value of theinfinite series
    ∞
    ∑
    .i fii =110
    ∑
    ∞
    A simple generating function argument shows that F x = , so substituting x = 1 / 10 ixi 2
    i =1
    1 − x − xleads 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 thei ′ ′
    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 . . . . Butsince 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.
Algebra Test 892