HMMT 二月 2003 · 团队赛 · 第 3 题
HMMT February 2003 — Team Round — Problem 3
题目详情
- (a) [15] Let A = { a , a , a , . . . , a , b } , for n ≥ 3, and let C be the 2-configuration n 1 2 3 n n consisting of { a , a } for all 1 ≤ i ≤ n − 1, { a , a } , and { a , b } for 1 ≤ i ≤ n . i i +1 1 n i Let S ( n ) be the number of subsets of C that are consistent of order e . Find e n S (101) for e = 1 , 2, and 3. e (b) [20] Let A = { V, W, X, Y, Z, v, w, x, y, z } . Find the number of subsets of the 2-configuration { { V, W } , { W, X } , { X, Y } , { Y, Z } , { Z, V } , { v, x } , { v, y } , { w, y } , { w, z } , { x, z } , { V, v } , { W, w } , { X, x } , { Y, y } , { Z, z } } that are consistent of order 1. (c) [30] Let A = { a , b , a , b , . . . , a , b } , and consider the 2-configuration C con- 1 1 2 2 10 10 sisting of { a , b } for all 1 ≤ i ≤ 10, { a , a } for all 1 ≤ i ≤ 9, and { b , b } for i i i i +1 i i +1 all 1 ≤ i ≤ 9. Find the number of subsets of C that are consistent of order 1. Define a k -configuration of A to be m -separable if we can label each element of A with an integer from 1 to m (inclusive) so that there is no element E of the k -configuration all of whose elements are assigned the same integer. If C is any subset of A , then C is m -separable if we can assign an integer from 1 to m to each element of C so that there is no element E of the k -configuration such that E ⊆ C and all elements of E are assigned the same integer. 1
解析
- (a) Let A = { a , a , a , . . . , a , b } , for n ≥ 3, and let C be the 2-configuration n 1 2 3 n n consisting of { a , a } for all 1 ≤ i ≤ n − 1, { a , a } , and { a , b } for 1 ≤ i ≤ n . i i +1 1 n i Let S ( n ) be the number of subsets of C that are consistent of order e . Find e n S (101) for e = 1 , 2, and 3. e 1 Solution: For convenience, we assume the a are indexed modulo 101, so that a = a i i +1 1 when a = a . i 101 In any consistent subset of C of order 1, b must be paired with exactly one a , say 101 i a . Then, a cannot be paired with a , so it must be paired with a , and likewise we find 1 2 1 3 we use the pairs { a , a } , { a , a } , . . . , { a , a } — and this does give us a consistent 4 5 6 7 100 101 subset of order 1. Similarly, pairing b with any other a would give us a unique extension i to a consistent configuration of order 1. Thus, we have one such 2-configuration for each i , giving S (101) = 101 altogether. 1 In a consistent subset of order 2, b must be paired with two other elements. Suppose one of them is a . Then a is also paired with either a or a , say a . But then i i i − 1 i +1 i +1 a needs to be paired up with two other elements, and a is not available, so it must i − 1 i be paired with a and b . Now b has its two pairs determined, so nothing else can be i − 2 paired with b . Thus, for j 6 = i − 1 , i , we have that a must be paired with a and j j − 1 a . So our subset must be of the form j +1 {{ b, a } , { a , a } , { a , a } , . . . , { a , a } , . . . , { a , a } , { a , b }} i i i +1 i +1 i +2 101 1 i − 2 i − 1 i − 1 for some i . On the other hand, for any i = 1 , . . . , 101, this gives a subset meeting our requirements. So, we have 101 possibilities, and S (101) = 101. 2 Finally, in a consistent subset of order 3, each a must be paired with a , a , i i − 1 i +1 and b . But then b occurs in 101 pairs, not just 3, so we have a contradiction. Thus, no such subset exists, so S (101) = 0. 3 (b) Let A = { V, W, X, Y, Z, v, w, x, y, z } . Find the number of subsets of the 2- configuration { { V, W } , { W, X } , { X, Y } , { Y, Z } , { Z, V } , { v, x } , { v, y } , { w, y } , { w, z } , { x, z } , { V, v } , { W, w } , { X, x } , { Y, y } , { Z, z } } that are consistent of order 1. Solution: No more than two of the pairs { v, x } , { v, y } , { w, y } , { w, z } , { x, z } may be included in a 2-configuration of order 1, since otherwise at least one of v, w, x, y, z would occur more than once. If exactly one is included, say { v, x } , then w, y, z must be paired with W, Y, Z , respectively, and then V and X cannot be paired. So either none or exactly two of the five pairs above must be used. If none, then v, w, x, y, z must be paired with V, W, X, Y, Z , respectively, and we have 1 2-configuration arising in this manner. If exactly two are used, we can check that there are 5 ways to do this without duplicating an element: { v, x } , { w, y } { v, x } , { w, z } { v, y } , { w, z } { v, y } , { x, z } { w, y } , { x, z } In each case, it is straightforward to check that there is a unique way of pairing up the remaining elements of A . So we get 5 2-configurations in this way, and the total is 6. (c) Let A = { a , b , a , b , . . . , a , b } , and consider the 2-configuration C consisting 1 1 2 2 10 10 of { a , b } for all 1 ≤ i ≤ 10, { a , a } for all 1 ≤ i ≤ 9, and { b , b } for all i i i i +1 i i +1 1 ≤ i ≤ 9. Find the number of subsets of C that are consistent of order 1. Solution: Let A = { a , b , a , b , . . . , a , b } for n ≥ 1, and consider the 2-configuration n 1 1 2 2 n n C consisting of { a , b } for all 1 ≤ i ≤ n , { a , a } for all 1 ≤ i ≤ n − 1, and { b , b } n i i i i +1 i i +1 2 for all 1 ≤ i ≤ n − 1. Let N be the number of subsets of C that are consistent of order n n 1 (call these “matchings” of C ). Consider any matching of C . Either a is paired n n +2 n +2 with b , in which case the remaining elements of our matching form a matching of n +2 C ; or a is paired with a , in which case b must be paired with b , and n +1 n +2 n +1 n +2 n +1 the remaining elements form a matching of C . It follows that N = N + N . By n n +2 n +1 n direct calculation, N = 1 and N = 2, and now computing successive values of N 1 2 n using the recurrence yields N = 89. 10 Define a k -configuration of A to be m -separable if we can label each element of A with an integer from 1 to m (inclusive) so that there is no element E of the k -configuration all of whose elements are assigned the same integer. If C is any subset of A , then C is m -separable if we can assign an integer from 1 to m to each element of C so that there is no element E of the k -configuration such that E ⊆ C and all elements of E are assigned the same integer.