HMMT 二月 2009 · TEAM1 赛 · 第 2 题

HMMT February 2009 — TEAM1 Round — Problem 2

(a) [ 4 ] Let P be a graph with one vertex v for each positive integer n . If a < b , then an edge n b connects vertices v and v if and only if is a prime number. What is the chromatic a b a number of P ? Prove your answer. (b) [ 6 ] Let T be a graph with one vertex v for every integer n . An edge connects v and v n a b if | a − b | is a power of two. What is the chromatic number of T ? Prove your answer.

解析

(a) [ 6 ] Let P be a graph with one vertex v for each positive integer n . If a < b , then an edge n b connects vertices v and v if and only if is a prime number. What is the chromatic a b a number of P ? Prove your answer. Answer: 2 Solution: At least two colors are needed in a good coloring of P . We show that two is e e e 1 2 k sufficient. Write the positive integer n as p p . . . p , for distinct primes p , p , . . . p , 1 2 k 1 2 k and let f ( n ) = e + e + . . . + e . Notice that if v and v are connected, then f ( a ) and 1 2 k a b f ( b ) have opposite parity. So, if we color v red if f ( n ) is odd and blue otherwise, the n two-coloring is good. (b) [ 6 ] Let T be a graph with one vertex v for every integer n . An edge connects v and v n a b if | a − b | is a power of two. What is the chromatic number of T ? Prove your answer. Answer: 3 Solution: Since v , v , and v are all connected to each other, three colors is necessary. 0 1 2 Now, color v red if n ≡ 0 (mod 3), blue if n ≡ 1 (mod 3), and green otherwise. Since n v and v are the same color only if 3 | ( a − b ), no two connected vertices are the same a b color.