2011 AMC 10A Problem 22

Question

Each vertex of convex pentagon

ABCDE

is to be assigned a color. There are

6

colors to choose from, and the ends of each diagonal must have different colors. How many different colorings are possible?

2520

2880

3120

3250

3750

Case on whether

5

,

4

, or

3

colors are used

Repeated colors can occur only on adjacent vertices

Note that there are only

3

cases: all the vertices are different, there is one pair of adjacent vertices with the same colors, or there are

2

pairs (each pair has a different color).

Case

1:

all vertices have different colors

This case just gives us

6! = 720

different colorings.

Case

2:

one pair of adjacent vertices has the same color

There are

\dfrac{6!}{2} = 360

ways to choose the colors for this case. There are then

5

options for the pair of vertices.

This gives us a total of

360 \cdot 5 = 1800

colorings for this case.

Case

3:

two pairs of adjacent vertices have the same color

There are

5

choices for the vertex that is not in a pair. There are then

6 \cdot 5 \cdot 4 = 120

choices for the colors. There are then a total of

120 \cdot 5 = 600

colorings for this case.

There are a total of

720 + 1800 + 600 = 3120

colorings for all the cases.

Thus, C is the correct answer.

Problem 22 in other years