HMMT 二月 2003 · 团队赛 · 第 10 题
HMMT February 2003 — Team Round — Problem 10
题目详情
- [45] Show that every consistent 2-configuration of order 4 on a finite set A has a subset that is a consistent 2-configuration of order 2. 2
解析
- Show that every consistent 2-configuration of order 4 on a finite set A has a subset that is a consistent 2-configuration of order 2. Solution: First, assume the 2-configuration has just one cell. We claim there exists a sequence 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 the longest 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 condition ensures such a maximal sequence exists.) Each element of A occurs an even number of times among these pairs (since each occurrence in the sequence contributes to two pairs). If every element occurs 4 times or 0 times, then the elements occurring in the sequence 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. i Choose b so that { a , b } is one of the two pairs in the 2-configuration not used by our 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, until k k k +1 we reach a point where finding another unused pair is impossible. Now, our pairs so far 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 is i used in three pairs, and b , which is used in an odd number of pairs (so one or three) — k unless a = b , in which case this element occurs four times. But since it is impossible i k to continue the sequence, b must indeed have been used four times, so b = a . k k i 7 But now we can construct the following sequence of distinct elements of the 2-configuration: { 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 means that 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’s second 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 1st, 3rd, 5th, . . . , (2 n − 1)th pairs, and then each element of A belongs to just two of these pairs, because each occurrence of the element as an a contributes to two consecutive i pairs from our original sequence (or the first and last such pairs). Thus, we have our consistent 2-configuration of order 2, as desired. Finally, if A consists of more than one cell, then the pairs within any given cell form a consistent 2-configuration of order 4 on that cell. So we simply apply the above procedure to obtain a consistent 2-configuration of order 2 on each cell, and then combining 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 the elements of graph theory, one of the major research areas of modern mathematics. What we 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 3b is the Petersen graph , a ubiquitous counterexample in graph theory. A consistent 2-configuration of 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