Each vertex of a convex pentagon PQRST is to be assigned a color, from an available choice of six distinct colors. The ends of each diagonal must be assigned a different color.

How many different colorings are possible?

A color can be repeated only once, and only if the repeated colors are directly adjacent to each other.

So there are three "types" of color configurations: those with two pairs or the same colors (e.g. blue-blue-red-red-green), those with one pair of the same color (e.g. blue-blue-red-green-yellow), and those with no pairs of the same color (e.g. blue-red-green-yellow-purple).

Of the first type, there are 6 possible choices for the color of the first pair, 5 possible choices for the color of the second pair, and 4 possible choices for the third solitary color, for a total of 6*5*4 = 120 permutations.  Each of these can be positioned in five different ways on the pentagon (e.g. the first pair can start on P-Q, or on Q-R, or R-S, etc.), so there are a total of 5*120 = 600 permutations of this type.

Of the second type, there are 6 possible choices for the color of the pair, and then 5, 4, and 3 choices for the remaining colors, respectively.  Additionally, there are once again 5 different ways that each of these configurations can be mapped onto the pentagon, so there are a total of 6*5*4*3*5 = 1800 permutations of this type.

Of the third type, there are 6*5*4*3*2 = 720 possible permutations.  For this type, we don't need to multiply by 5 because this number already accounts for different positions of the same 5-color string (e.g. blue-red-green-yellow-purple and red-green-yellow-purple-blue have both already been counted). 

So the total number of possible colorings is 600 + 1800 + 720 = 3120.

Posted by tomarken on 2014-07-18 10:14:56