HMMT 二月 2003 · 团队赛 · 第 3 题

英文解析

3. (a) Let A = { a , a , a , . . . , a , b } , for n ≥ 3, and let C be the 2-configurationn 1 2 3 n nconsisting 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 . Finde n
   S (101) for e = 1 , 2, and 3.
   1 e
   Solution: For convenience, we assume the a are indexed modulo 101, so that a = ai 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 ia . 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 extensionito a consistent configuration of order 1. Thus, we have one such 2-configuration for eachi , giving S (101) = 101 altogether.
   In a consistent subset of order 2, b must be paired with two other elements. Suppose 1
   one of them is a . Then a is also paired with either a or a , say a . But theni i i − 1 i +1 i +1
   a needs to be paired up with two other elements, and a is not available, so it musti − 1 ibe paired with a and b . Now b has its two pairs determined, so nothing else can bei − 2
   paired with b . Thus, for j 6 = i − 1 , i , we have that a must be paired with a andj j − 1
   a . So our subset must be of the formj +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 ourrequirements. So, we have 101 possibilities, and S (101) = 101.
   Finally, in a consistent subset of order 3, each a must be paired with a , a ,2
   i i − 1 i +1
   and b . But then b occurs in 101 pairs, not just 3, so we have a contradiction. Thus, nosuch subset exists, so S (101) = 0.
   (b) Let A = { V, W, X, Y, Z, v, w, x, y, z } . Find the number of subsets of the 2-3
   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 beincluded in a 2-configuration of order 1, since otherwise at least one of v, w, x, y, z wouldoccur more than once. If exactly one is included, say { v, x } , then w, y, z must be pairedwith W, Y, Z , respectively, and then V and X cannot be paired. So either none orexactly two of the five pairs above must be used. If none, then v, w, x, y, z must bepaired with V, W, X, Y, Z , respectively, and we have 1 2-configuration arising in thismanner. If exactly two are used, we can check that there are 5 ways to do this withoutduplicating 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 theremaining 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 alli 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-configurationn 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
   for all 1 ≤ i ≤ n − 1. Let N be the number of subsets of C that are consistent of order 2
   n n
   1 (call these “matchings” of C ). Consider any matching of C . Either a is pairedn n +2 n +2
   with b , in which case the remaining elements of our matching form a matching ofn +2
   C ; or a is paired with a , in which case b must be paired with b , andn +1 n +2 n +1 n +2 n +1
   the remaining elements form a matching of C . It follows that N = N + N . Byn n +2 n +1 ndirect calculation, N = 1 and N = 2, and now computing successive values of N
   1 2 nusing the recurrence yields N = 89.
   Define a k -configuration of A to be m -separable if we can label each element of A with an 10
   integer from 1 to m (inclusive) so that there is no element E of the k -configuration all ofwhose elements are assigned the same integer. If C is any subset of A , then C is m -separableif we can assign an integer from 1 to m to each element of C so that there is no element Eof the k -configuration such that E ⊆ C and all elements of E are assigned the same integer.