HMMT 十一月 2016 · THM 赛 · 第 9 题

英文解析

9. The vertices of a regular nonagon are colored such that 1) adjacent vertices are different colors and 2)
   if 3 vertices form an equilateral triangle, they are all different colors.
   Let m be the minimum number of colors needed for a valid coloring, and n be the total number ofcolorings using m colors. Determine mn . (Assume each vertex is distinguishable.)
   Proposed by: Eshaan Nichani
   Answer: 54
   It’s clear that m is more than 2 since it’s impossible to alternate the color of the vertices withouthaving two of the same color adjacent (since the graph is not bipartite). However, it’s possible to use
   3 colors. Number the vertices 1 through 9 in order and let the colors be A, B, C . Coloring the verticesin the order BCBCACABA gives a configuration that works, so m is 3. To determine n , we canpartition the nonagon into three equilateral triangles. Vertices 1 , 4 , 7 must be different colors, whichwe can choose in 3! = 6 ways. Suppose WLOG that they’re A, B, C respectively. Then we look atvertices 2 , 5 , 8. Vertex 2 can be colored B or C . If 2 is B , then vertex 8 must be A , and vertex 5 must be C . In this case there are two ways to color the remaining vertices 3 , 6 , 9. Otherwise, if vertex 2 is
   C , then vertex 5 must be A , and vertex 8 must be B . This gives us only 1 possible coloring for theremaining three vertices. So n is 6(2 + 1) = 18. So our answer is mn = 54.