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

英文解析

10. Show that every consistent 2-configuration of order 4 on a finite set A has a subsetthat is a consistent 2-configuration of order 2.
    Solution: First, assume the 2-configuration has just one cell. We claim there exists asequence a , a , . . . , a of elements of A (not necessarily all distinct) such that the list
    0 1 n
    { a , a } , { a , a } , . . . , { a , a } , { a , a }
    0 1 1 2 n − 1 n n 0
    contains each element of the 2-configuration exactly once. To see this, consider thelongest sequence such that { a , a } , . . . , { a , a } , { a , a } are all distinct elements of
    0 1 n − 1 n n 0
    the 2-configuration. (We may take n = 0 if necessary. Note that the finiteness conditionensures such a maximal sequence exists.) Each element of A occurs an even numberof times among these pairs (since each occurrence in the sequence contributes to twopairs). If every element occurs 4 times or 0 times, then the elements occurring in thesequence form a cell, since they cannot occur in any other pairs in the 2-configuration.
    Hence, they are all of A , and our sequence uses all the pairs in the 2-configuration,
    so the claim follows. Otherwise, there is some element a occurring exactly twice.
    Choose b so that { a , b } is one of the two pairs in the 2-configuration not used by ouri
    1 i 1
    sequence. Then choose b so that { b , b } be another pair not used thus far. Continue
    2 1 2
    in this manner, choosing new elements b with { b , b } a pair not already used, untilk k k +1
    we reach a point where finding another unused pair is impossible. Now, our pairs sofar are
    { a , a } , . . . , { a , a } , { a , a } ,
    0 1 n − 1 n n 0
    { a , b } , { b , b } , . . . , { b , b } .
    i 1 1 2 k − 1 k
    Every element is used in an even number of these pairs, except possibly a , which isiused in three pairs, and b , which is used in an odd number of pairs (so one or three) —
    unless a = b , in which case this element occurs four times. But since it is impossibleki kto continue the sequence, b must indeed have been used four times, so b = a .
    k k i
    But now we can construct the following sequence of distinct elements of the 2-configuration:7
    { a , a } , . . . , { a , a } , { a , b } , { b , b } , . . . , { b , a } ,
    0 1 i − 1 i i 1 1 2 k − 1 i
    { a , a } , . . . , { a , a } , { a , a } .
    i i +1 n − 1 n n 0
    This contradicts the maximality of our original sequence. This contradiction meansthat our original sequence must have used all the pairs in the 2-configuration, after all.
    So we can express the 2-configuration via such a sequence of pairs, where each pair’ssecond element equals the first element of the next pair. If A has n elements, then
    (since each element appears in four pairs) we have 2 n pairs. So we can choose the 1 st,
    3 rd, 5 th, . . . , (2 n − 1)th pairs, and then each element of A belongs to just two of thesepairs, because each occurrence of the element as an a contributes to two consecutivepairs from our original sequence (or the first and last such pairs). Thus, we have ouriconsistent 2-configuration of order 2, as desired.
    Finally, if A consists of more than one cell, then the pairs within any given cell forma consistent 2-configuration of order 4 on that cell. So we simply apply the aboveprocedure to obtain a consistent 2-configuration of order 2 on each cell, and thencombining these gives a consistent 2-configuration of order 2 on A , as desired.
    Comments: A note for those who might have found these problems rather foreign
    — the objects described here are actually of considerable importance; they constitute theelements of graph theory, one of the major research areas of modern mathematics. Whatwe have called a “2-configuration” is generally called a graph , and what we have called a
    “ k -configuration” ( k > 2) is generally called a hypergraph . The graph in problem 3 b is the
    Petersen graph , a ubiquitous counterexample in graph theory. A consistent 2-configurationof order n is an n -regular graph; a cell is a component ; a barren 2-configuration is a forest
    (and a forest with one component is a tree ); and an m -separable configuration is m -colorable
    (and the minimum m for which a graph is m -colorable is its chromatic number ). 8