HMMT 二月 2011 · TEAM1 赛 · 第 14 题

英文解析

14. [ 25 ] Given a positive integer n , a sequence of integers a , a , . . . , a , where 0 ≤ a ≤ k for all 1 ≤ i ≤ r ,
    1 2 r iis said to be a “ k -representation ” of n if there exists an integer c such thatr r
    ∑ ∑
    c − ia = a k = n.
    i ii =1 i =1
    Prove that every positive integer n has a k -representation , and that the k -representation is unique ifand only if 0 does not appear in the base- k representation of n − 1.
    Solution: Given a positive integer n , a sequence of integers a , a , . . . , a , where 0 ≤ a ≤ k for all
    1 2 r i
    1 ≤ i ≤ r , is said to be a “ k -representation ” of n if there exists an integer c such thatr r
    ∑ ∑
    c − ia = a k = n.
    i ii =1 i =1
    Prove that every positive integer n has a k -representation , and that the k -representation is unique ifand only if 0 does not appear in the base- k representation of n − 1.
    Equivalently, a k -representation is given by a sequence a , . . . , a , for some p < q , such thatp qq q
    ∑ ∑
    a = a k .ii ii = p i = p
    ∑
    We first show existence. Let the representation of n − 1 in base k be given by a k = n − 1.irii =0
    ∑
    i − 1 i − 2 r
    Let l = a ( k + k + · · · + 1). Now we extend the sequence { a } by letting a = k − 1 ifi i ii =1 − l + 1 ≤ i ≤ − 1 and a = k . We claim that a , . . . , a , a is a k -representation of n . Indeed,
    − l − l r − 1 r
    ( )
    r − 1
    ∑ ∑
    i i − la k = ( n − 1) + ( k − 1) n + ki = − l i = − li − l
    1 − k − 1 − l = ( n − 1) + ( k − 1) k + k = n − 1
    1 − k
    ( )
    r r
    ∑ ∑
    a = a + l ( k − 1) + 1
    i ii =0
    i = − l
    ( ) ( )
    r r
    ∑ ∑
    = a + a ( k − 1) + 1 ii ii =0 i =1
    ( )
    ∑ri = a k + 1 = nii =0
    Team Round A
    ∑ ∑
    Now suppose there is another k -representation { b } of n ; then b = b k = n. This implies thatii i i
    ∑ ∑
    c = c k = 0 where c = a − b . The following claim specifies all possibilities of { c } .ii i i i i i
    ∑
    Claim: Suppose that c k = 0, where c , p, q ∈ Z , p < q , and c ∈ [ − k, k ]. Then the sequence { c }iqi i i ii = pmust be the concatenation of subsequences of the form
    ± (1 , 1 − k, 1 − k, . . . , 1 − k, − k )
    , possibly with 0’s in between.
    Proof. If c is not the zero sequence, then without loss of generality, we may assume c > 0.
    i q
    ∑
    Since c k = 0, we haveiqii = pkq q − 1 p q q − 1 p +1 q q
    | c k | = | c k + . . . + c k | ≤ k + k + . . . + k < k ≤ 2 kq q − 1 pk − 1
    so c = 1. Now we haveqq q − 1 pk + c k + . . . + c k = 0 . (1)
    q − 1 pq − 1 p
    This means ( k + c ) k + . . . + c k = 0. Hence, as above,
    q − 1 pq − 1 q − 2 p q − 1
    | ( k + c ) k | = | c k + . . . + c k | < 2 k .
    q − 1 q − 2 p
    Therefore, | ( k + c ) | < 2, which means c = − k or − k + 1.
    q − 1 q − 1
    q q − 1
    If c = − k , then c k + c k = 0, and we get a subsequence (1 , − k ).
    q − 1 q q − 1
    q q − 1 q − 1
    If c = − k + 1, then c k + c k = k . Thusq − 1 q q − 1
    q − 1 q − 2 pk + c k + . . . + c k = 0 ,
    q − 2 pwhich has the exact same form as (1). We can then repeat this procedure to obtain a subsequence
    (1 , 1 − k, 1 − k, . . . , 1 − k, − k ).
    ∑
    Once we have such a subsequence, the terms in the sum c k = 0 corresponding to that subse-iqii = pquence sum to 0, so we may remove them and apply the same argument.
    We now consider the cases.
    If the base k representation of n − 1 contains no 0’s, then a 6 = 0 so it is impossible to have c = a − b =
    i i i i − k . On the other hand, we know that c is composed of subsequences of the form ± (1 , 1 − k, 1 − k, . . . , 1 −
    ∑ik, − k ). Therefore, if { c } is not the zero sequence, then the fact that c = 0 implies that we musti ihave both a subsequence (1 , 1 − k, 1 − k, . . . , 1 − k, − k ) and a subsequence − (1 , 1 − k, 1 − k, . . . , 1 − k, − k ),
    meaning that there exists i for which c = − k , contradiction.
    If the base k representation of n − 1 contains a 0, then picking the largest i such that a = 0, weiican change a to k and a to a − 1, and append a (1 , − k ) to the end of the sequence. Thisi i +1 i +1
    yields another k -representation of n , so a k -representation of n is unique if and only if the base krepresentation of n − 1 contains no 0’s, as desired.