AMC10 2011 A

AMC10 2011 A · Q22

AMC10 2011 A · Q22. It mainly tests Combinations, Circle theorems.

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?

凸五边形 $ABCDE$ 的每个顶点都要涂上颜色。有6种颜色可供选择，且每条对角线的两端必须涂不同颜色。可能的不同着色方案有多少种？

(A) 2520 2520

(B) 2880 2880

(D) 3250 3250

(E) 3750 3750

Answer

Correct choice: (C)

正确答案：（C）

Solution

Answer (C): If five distinct colors are used, then there are $\binom{6}{5}=6$ different color choices possible. They may be arranged in $5!=120$ ways on the pentagon, resulting in $120\cdot 6=720$ colorings. If four distinct colors are used, then there is one duplicated color, so there are $\binom{6}{4}\binom{4}{1}=60$ different color choices possible. The duplicated color must appear on neighboring vertices. There are $5$ neighbor choices and $3!=6$ ways to color the remaining three vertices, resulting in a total of $60\cdot 5\cdot 6=1800$ colorings. If three distinct colors are used, then there must be two duplicated colors, so there are $\binom{6}{3}\binom{3}{2}=60$ different color choices possible. The non-duplicated color may appear in $5$ locations. As before, a duplicated color must appear on neighboring vertices, so there are $2$ ways left to color the remaining vertices. In this case there are $60\cdot 5\cdot 2=600$ colorings possible. There are no colorings with two or fewer colors. The total number of colorings is $720+1800+600=3120$.

答案（C）：如果使用五种不同的颜色，则有 $\binom{6}{5}=6$ 种不同的选色方式。它们可以在五边形上以 $5!=120$ 种方式排列，因此共有 $120\cdot 6=720$ 种着色。如果使用四种不同的颜色，则会有一种颜色重复，因此有 $\binom{6}{4}\binom{4}{1}=60$ 种不同的选色方式。重复的颜色必须出现在相邻的顶点上。相邻顶点的选择有 $5$ 种，剩下三个顶点的着色有 $3!=6$ 种方式，因此总共有 $60\cdot 5\cdot 6=1800$ 种着色。如果使用三种不同的颜色，则必须有两种颜色重复，因此有 $\binom{6}{3}\binom{3}{2}=60$ 种不同的选色方式。不重复的那种颜色可以放在 $5$ 个位置中的任意一个。和之前一样，重复颜色必须出现在相邻顶点上，因此剩余顶点的着色还有 $2$ 种方式。在这种情况下共有 $60\cdot 5\cdot 2=600$ 种着色。不存在只用两种或更少颜色的着色。着色总数为 $720+1800+600=3120$。

Topics