2011 AMC 10A Problems/Problem 22

Problem 22

Each vertex of convex pentagon is to be assigned a color. There are colors to choose from, and the ends of each diagonal must have different colors. How many different colorings are possible?

Solution 1

Let vertex be any vertex, then vertex be one of the diagonal vertices to , be one of the diagonal vertices to , and so on. We consider cases for this problem.

In the case that has the same color as , has a different color from and so has a different color from and . In this case, has choices, has choices (any color but the color of ), has choice, has choices, and has choices, resulting in a possible of combinations.

In the case that has a different color from and has a different color from , has choices, has choices, has choices (since and necessarily have different colors), has choices, and has choices, resulting in a possible of combinations.

In the case that has a different color from and has the same color as , has choices, has choices, has choices, has choice, and has choices, resulting in a possible of combinations.

Adding all those combinations up, we get .

Solution 2

First, notice that there can be cases. One with all vertices painted different colors, one with one pair of adjacent vertices painted the same color and the final one with two pairs of adjacent vertices painted two different colors.

Case : There are ways of assigning each vertex a different color.

Case : There are ways. After picking four colors, we can rotate our pentagon in ways to get different outcomes.

Case : There are ways of arranging the final case. We can pick colors for our pentagon. There are spots for the first pair of colors. Then, there are possible ways we can put the final pair in the last spaces. But because the two pairs are indistinguishable, we divide by .

Adding all the possibilities up, we get

~ZericHang

See Also

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.