HMMT 二月 2014 · 团队赛 · 第 2 题

2 . Let ( b , b , . . . , b ) be a set of positive integers such that 3 b ≤ b for all i . The sets {| a − a | , | a − 1 2 n i i +1 1 0 2 a | , . . . , | a − a | , | a − a |} and { b , b , . . . , b } are equal. 1 n − 1 n − 2 n n − 1 1 2 n Then, the number of great sequences is ( n + 1)!. If we prove this statement, then we can just consider the specific case of b = 1, 3 b = b to solve 1 i i +1 our problem. Before we proceed, we will prove a lemma. Lemma: Let ( b , b , . . . , b ) be a set of positive integers such that 3 b ≤ b for all i . Then b > 1 2 n i i +1 i i − 1 ∑ 2 b . k k =1 i − 1 ∑ b b b i i i Proof: = + + · · · ≥ b . Equality only occurs when the sequence b is infinite, which is not k i 2 3 9 k =1 the case, so the inequality holds. We can now proceed with the induction. The base case is obvious. Assume it is true up to n = j − 1. Next, consider some permutation of the set B = { b , b , b , · · · , b } . Denote it as C = { c , c , . . . , c } . 1 2 3 j 1 2 j Find the element c = b . For the first k − 1 elements of C , we can put them in order and apply k j the inductive hypothesis. The number of great sequences such that the set of differences {| a − 1 a | , . . . , | a − a |} is equal to { c , c , . . . , c } is k !. 0 k − 1 k − 2 1 2 k − 1 k − 1 ∑ Then, a can be either a + c or a − c . This is because, by the lemma, c > 2 c = k k − 1 k k − 1 k k m m =1 k − 1 ∑ 2 | a − a | ≥ 2 | a − a + a − a + · · · + a − a | = 2 | a | . It is easy to check that for m m − 1 k − 1 k − 2 k − 2 k − 3 1 0 k − 1 m =1 either possible value of a , | a | > | a | . After that, there is only one possible value for a , . . . , a k k k − 1 k +1 j because only one of a ± c will satisfy | a | > | a | . i i +1 i i − 1 ( ) j − 1 There are possible ways to choose c , c , . . . , c from B . Given those elements of C , there are 1 2 k − 1 k − 1 k ! ways to make a great sequence ( a , a , . . . , a ). Then, there are 2 possible values for a . After 0 1 k − 1 k that, there are ( j − k )! ways to order the remaining elements of C , and for each such ordering, there is exactly 1 possible great sequence ( a , a , . . . , a ). 0 1 j Now, counting up all the possible ways to do this over all values of k , we get that the number of great j j ( ) ∑ ∑ j ( j +1) j − 1 sequences is equal to k !2( j − k )! = 2( j − 1)!( k ) = 2( j − 1)! = ( j + 1)!. The induction k − 1 2 k =1 k =1 is complete, and this finishes the proof. Alternate solution : Another method of performing the induction is noting that any acceptable se- quence ( a , . . . , a ) can be matched with n + 2 acceptable sequences of length n + 2 because we can 0 n take (3 a , . . . , 3 a ) and add an element with a difference of 1 in any of n + 2 positions. 0 n