HMMT 二月 2009 · TEAM1 赛 · 第 2 题

英文解析

2. (a) [ 6 ] Let P be a graph with one vertex v for each positive integer n . If a < b , then an edgenconnects vertices v and v if and only if is a prime number. What is the chromaticbanumber of P ? Prove your answer.ab
   Answer: 2
   Solution: At least two colors are needed in a good coloring of P . We show that two isee e
   1 2 ksufficient. Write the positive integer n as p p . . . p , for distinct primes p , p , . . . p ,
   1 2 k
   1 2
   and let f ( n ) = e + e + . . . + e . Notice that if v and v are connected, then f ( a ) andk
   1 2 k a bf ( b ) have opposite parity. So, if we color v red if f ( n ) is odd and blue otherwise, thetwo-coloring is good.n
   (b) [ 6 ] Let T be a graph with one vertex v for every integer n . An edge connects v and vn a bif | 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. Sincenv and v are the same color only if 3 | ( a − b ), no two connected vertices are the sameacolor.b