HMMT 二月 2009 · TEAM1 赛 · 第 7 题

英文解析

7. [ 20 ] Let n be a positive integer. Let V be the set of all sequences of 0’s and 1’s of length n .
   Define G to be the graph having vertex set V , such that two sequences are adjacent in Gnn n nif and only if they differ in either 1 or 2 places. For instance, if n = 3, the sequences (1 , 0 , 0),
   (1 , 1 , 0), and (1 , 1 , 1) are mutually adjacent, but (1 , 0 , 0) is not adjacent to (0 , 1 , 1).
   Show that, if n + 1 is not a power of 2, then the chromatic number of G is at least n + 2.
   Solution: We will assume that there is a coloring with n +1 colors and derive a contradiction.n
   For each string s , let T be the set consisting of all strings that differ from s in at most 1
   place. Thus T has size n + 1 and all vertices in T are adjacent. In particular, if there is anss s
   ( n + 1)-coloring, then each color is used exactly once in T . Let c be one of the colors that wesused. We will determine how many vertices are colored with c . We will do this by countingin two ways.
   Let k be the number of vertices colored with color c . Each such vertex is part of T for exactlysn + 1 values of s . On the other hand, each T contains exactly one vertex with color c . Itsn nfollows that k ( n + 1) = 2 . In particular, since k is an integer, n + 1 divides 2 . This isa contradiction since n + 1 is now a power of 2 by assumption, so actually there can be non + 1-coloring, as claimed.