All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Vertex Coloring Conclusion (Posted on 2014-07-18) Difficulty: 3 of 5
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?

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Possible solution Comment 2 of 2 |

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
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information