HMMT 二月 2013 · 冲刺赛 · 第 21 题
HMMT February 2013 — Guts Round — Problem 21
题目详情
- [ 14 ] Find the number of positive integers j ≤ 3 such that m ( ) ∑ k a k j = ( − 1) · 3 k =0 1 for some strictly increasing sequence of nonnegative integers { a } . For example, we may write 3 = 3 k 0 3 4 and 55 = 3 − 3 + 3 , but 4 cannot be written in this form.
解析
- [ 14 ] Find the number of positive integers j ≤ 3 such that m ( ) ∑ k a k j = ( − 1) · 3 k =0 1 for some strictly increasing sequence of nonnegative integers { a } . For example, we may write 3 = 3 k 0 3 4 and 55 = 3 − 3 + 3 , but 4 cannot be written in this form. 2013 Answer: 2 Clearly m must be even, or the sum would be negative. Furthermore, if a ≤ 2013, m ( ) ∑ m − 1 k 2013 a a a m k m the sum cannot exceed 3 since j = 3 + ( − 1) · 3 ≤ 3 . Likewise, if a > 2013, then m k =0 2013 the sum necessarily exceeds 3 , which is not hard to see by applying the Triangle Inequality and summing a geometric series. Hence, the elements of { a } can be any subset of { 0 , 1 , . . . , 2013 } with an k odd number of elements. Since the number of even-sized subsets is equal to the number of odd-sized 2014 2 2013 elements, there are = 2 such subsets. 2 Now, it suffices to show that given such an { a } , the value of j can only be obtained in this way. Suppose k for the the sake of contradiction that there exist two such sequences { a } and { b } k 0 ≤ k ≤ m k 0 ≤ k ≤ m a b which produce the same value of j for j positive or negative, where we choose { a } , { b } such that k k a a ( a − 1) 0 1 0 1 ma min( m , m ) is as small as possible. Then, we note that since 3 + 3 + . . . + 3 ≤ 3 + 3 + a b ( ) ∑ m k a ( a ) ( a − 1) a ( a − 1) ma − 1 ma k ma . . . + 3 < 2(3 ), we have that ( − 1) · 3 > 3 . Similarly, we get that k =0 ( ) ∑ m k b ( a − 1) a ( m − 1) m k b b 3 ≥ ( − 1) · 3 > 3 ; for the two to be equal, we must have m = m . However, a b k =0 this means that the sequences obtained by removing a and a from { a } { b } have smaller maximum m m k k a b value but still produce the same alternating sum, contradicting our original assumption. Guts Round