HMMT 二月 2011 · TEAM1 赛 · 第 14 题
HMMT February 2011 — TEAM1 Round — Problem 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 i is said to be a “ k -representation ” of n if there exists an integer c such that r r ∑ ∑ c − i a = a k = n. i i i =1 i =1 Prove that every positive integer n has a k -representation , and that the k -representation is unique if and only if 0 does not appear in the base- k representation of n − 1.
解析
- [ 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 i is said to be a “ k -representation ” of n if there exists an integer c such that r r ∑ ∑ c − i a = a k = n. i i i =1 i =1 Prove that every positive integer n has a k -representation , and that the k -representation is unique if and 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 that r r ∑ ∑ c − i a = a k = n. i i i =1 i =1 Prove that every positive integer n has a k -representation , and that the k -representation is unique if and 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 that p q q q ∑ ∑ i a = a k . i i i = p i = p ∑ r i We first show existence. Let the representation of n − 1 in base k be given by a k = n − 1. i i =0 ∑ r i − 1 i − 2 Let l = a ( k + k + · · · + 1). Now we extend the sequence { a } by letting a = k − 1 if i i i i =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 − l a k = ( n − 1) + ( k − 1) n + k i i = − l i = − l − l 1 − k − 1 − l = ( n − 1) + ( k − 1) k + k = n − 1 1 − k ( ) r r ∑ ∑ a = a + l ( k − 1) + 1 i i i =0 i = − l ( ) ( ) r r ∑ ∑ i = a + a ( k − 1) + 1 i i i =0 i =1 ( ) r ∑ i = a k + 1 = n i i =0 Team Round A ∑ ∑ i Now suppose there is another k -representation { b } of n ; then b = b k = n. This implies that i i i ∑ ∑ i c = c k = 0 where c = a − b . The following claim specifies all possibilities of { c } . i i i i i i ∑ q i Claim: Suppose that c k = 0, where c , p, q ∈ Z , p < q , and c ∈ [ − k, k ]. Then the sequence { c } i i i i i = p must 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 ∑ q i Since c k = 0, we have i i = p k q q − 1 p q q − 1 p +1 q q | c k | = | c k + . . . + c k | ≤ k + k + . . . + k < k ≤ 2 k q q − 1 p k − 1 so c = 1. Now we have q q q − 1 p k + c k + . . . + c k = 0 . (1) q − 1 p q − 1 p This means ( k + c ) k + . . . + c k = 0. Hence, as above, q − 1 p q − 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 . Thus q − 1 q q − 1 q − 1 q − 2 p k + c k + . . . + c k = 0 , q − 2 p which 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 ). ∑ q i Once we have such a subsequence, the terms in the sum c k = 0 corresponding to that subse- i i = p quence 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 − i ∑ k, − k ). Therefore, if { c } is not the zero sequence, then the fact that c = 0 implies that we must i i have 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. i If the base k representation of n − 1 contains a 0, then picking the largest i such that a = 0, we i can change a to k and a to a − 1, and append a (1 , − k ) to the end of the sequence. This i i +1 i +1 yields another k -representation of n , so a k -representation of n is unique if and only if the base k representation of n − 1 contains no 0’s, as desired.