Question

凸五边形 $ABCDE$ 的每个顶点都要指定一种颜色。有 $6$ 种颜色可选，并且每条对角线的两个端点必须颜色不同。有多少种不同的着色方法？

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$

答案：C

知识点：图论分类讨论排列

难度评级：1840

解答：

只有 $3$ 种情况：所有顶点颜色都不同；恰有一对相邻顶点同色；或有 $2$ 对相邻顶点同色，且两对使用不同颜色。

情况 $1$ 所有顶点颜色都不同。

此时有 $6! = 720$ 种着色方法。

情况 $2$ 恰有一对相邻顶点同色。

选择各顶点颜色的方式有种，而同色的相邻顶点对有 $5$ 种选择。 $\dfrac{6!}{2} = 360$

因此这种情况共有种着色方法。 $360 \cdot 5 = 1800$

情况 $3$ 有两对相邻顶点分别同色。

不在任何同色对中的顶点有 $5$ 种选择。再为两对和该单独顶点选择三种不同颜色，有种，所以这种情况共有种着色方法。 $6 \cdot 5 \cdot 4 = 120$ $120 \cdot 5 = 600$

所有情况合计种。 $720 + 1800 + 600 = 3120$

所以正确答案是 C。

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.

2011 AMC 10A 第 22 题

答案：C

难度评级：1840

解答：

其他年份的第 22 题