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

HMMT November 2016 — THM Round — Problem 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 of colorings using m colors. Determine mn . (Assume each vertex is distinguishable.)

解析

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 of colorings 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 without having 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 vertices in the order BCBCACABA gives a configuration that works, so m is 3. To determine n , we can partition the nonagon into three equilateral triangles. Vertices 1 , 4 , 7 must be different colors, which we can choose in 3! = 6 ways. Suppose WLOG that they’re A, B, C respectively. Then we look at vertices 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 the remaining three vertices. So n is 6(2 + 1) = 18. So our answer is mn = 54.