HMMT 二月 2009 · TEAM1 赛 · 第 7 题

HMMT February 2009 — TEAM1 Round — Problem 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 . n Define G to be the graph having vertex set V , such that two sequences are adjacent in G n n n if 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. n

解析

[ 20 ] Let n be a positive integer. Let V be the set of all sequences of 0’s and 1’s of length n . n Define G to be the graph having vertex set V , such that two sequences are adjacent in G n n n if 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. n Solution: We will assume that there is a coloring with n +1 colors and derive a contradiction. For each string s , let T be the set consisting of all strings that differ from s in at most 1 s place. Thus T has size n + 1 and all vertices in T are adjacent. In particular, if there is an s s ( n + 1)-coloring, then each color is used exactly once in T . Let c be one of the colors that we s used. We will determine how many vertices are colored with c . We will do this by counting in two ways. Let k be the number of vertices colored with color c . Each such vertex is part of T for exactly s n + 1 values of s . On the other hand, each T contains exactly one vertex with color c . It s n n follows that k ( n + 1) = 2 . In particular, since k is an integer, n + 1 divides 2 . This is a contradiction since n + 1 is now a power of 2 by assumption, so actually there can be no n + 1-coloring, as claimed.