Question

下图显示了一个由六个小区域组成的环，你要把它画在墙上。你有四种油漆颜色可用，并将每个小区域涂成一种纯色。如果相邻的两个区域不能涂成同一种颜色，求涂色方案的数量。

The figure below shows a ring made of six small sections which you are to paint on a wall. You have four paint colors available and will paint each of the six sections a solid color. Find the number of ways you can choose to paint the sections if no two adjacent sections can be painted with the same color.

答案

答案：732

知识点：图论递推计数

难度评级：2400

解答：

令 $P_n$ 为 $n$ 个区域构成的环的合法涂色数。把环在两个相邻区域之间剪开，可知环的涂色正好对应于一排 $n$ 个区域的涂色，其中相邻颜色不同，并且两个端点颜色也不同。一排 $n$ 个区域若相邻颜色不同，可用 $4 \cdot 3^{n-1}$ 种方式涂色；而两个端点颜色相同的行涂色，通过把两个端点区域合并为一个区域，对应于 $n - 1$ 个区域的环涂色。因此 $P_n + P_{n-1} = 4 \cdot 3^{n-1}.$

三个两两相邻的区域给出 $P_3 = 4 \cdot 3 \cdot 2 = 24$ ，所以 $P_4 = 108 - 24 = 84$ ，接着 $P_5 = 324 - 84 = 240$ ，最后 $P_6 = 972 - 240 = 732$ 。

Let $P_n$ be the number of valid paintings of a ring of $n$ sections. Cutting a ring open between two adjacent sections shows that ring paintings correspond exactly to rows of $n$ sections with adjacent colors different and the two end colors different. A row of $n$ sections with adjacent colors different can be painted in $4 \cdot 3^{n-1}$ ways, and the rows whose end colors match correspond, by merging the two end sections into one, to ring paintings of $n - 1$ sections. Hence $P_n + P_{n-1} = 4 \cdot 3^{n-1}.$

Three mutually adjacent sections give $P_3 = 4 \cdot 3 \cdot 2 = 24,$ so $P_4 = 108 - 24 = 84,$ then $P_5 = 324 - 84 = 240,$ and finally $P_6 = 972 - 240 = 732.$

2016 AIME II 第 12 题

答案：732

难度评级：2400

解答：

其他年份的第 12 题