2011 AMC 12A Problems/Problem 16

Problem

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

We can do some casework when working our way around the pentagon from to . At each stage, there will be a makeshift diagram.

1.) For , we can choose any of the 6 colors.

        A : 6

2.) For , we can either have the same color as , or any of the other 5 colors. We do this because each vertex of the pentagon is affected by the 2 opposite vertices, and will be affected by both and .

      A : 6
 B:1        B:5

3.) For , we cannot have the same color as . Also, we can have the same color as ( will be affected), or any of the other 4 colors. Because can't be the same as , it can't be the same as if is the same as , so it can be any of the 5 other colors.

      A : 6
 B:1        B:5
 C:5     C:4   C:1

4.) is affected by and . If they are the same, then can be any of the other 5 colors. If they are different, then can be any of the (6-2)=4 colors.

      A : 6
 B:1        B:5
 C:5     C:4   C:1
 D:5     D:4   D:4

5.) is affected by and . If they are the same, then can be any of the other 5 colors. If they are different, then can be any of the (6-2)=4 colors.

      A : 6
 B:1        B:5
 C:5     C:4   C:1
 D:5     D:4   D:4
 E:4     E:4   E:5

6.) Now, we can multiply these three paths and add them:

7.) Our answer is !