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 ii − 1
∑
2 b .
k =1 ki − 1
∑
b b bi i i
Proof: = + + · · · ≥ b . Equality only occurs when the sequence b is infinite, which is notk 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 applyk jthe inductive hypothesis. The number of great sequences such that the set of differences {| a −
a | , . . . , | a − a |} is equal to { c , c , . . . , c } is k !.1
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 mm =1
k − 1
∑
2 | a − a | ≥ 2 | a − a + a − a + · · · + a − a | = 2 | a | . It is easy to check that form 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 , . . . , ak k k − 1 k +1 jbecause 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 kthat, there are ( j − k )! ways to order the remaining elements of C , and for each such ordering, thereis 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 greatj j
( )
∑ ∑
j ( j +1)
j − 1
sequences is equal to k !2( j − k )! = 2( j − 1)!( k ) = 2( j − 1)! = ( j + 1)!. The inductionk − 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 sequence ( a , . . . , a ) can be matched with n + 2 acceptable sequences of length n + 2 because we can
0 ntake (3 a , . . . , 3 a ) and add an element with a difference of 1 in any of n + 2 positions.
0 n