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.)
Solution
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 B C B C A C A B A 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.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.