美国的数学竞赛难不难看看这道题就知道了

今天的题目是排列组合问题，来自美国的一次数学学术活动，解题所用知识不超过小学5年级。

题目（5星难度）：有一个九边形的各边长均不相同，用3种不同的颜色，给9条边染色，要求每条边只染一种颜色，且相邻2条边的颜色不同。有多少种不同的染色方法？

辅导方法：

将题目写给小朋友，让他自行思考解答，若20分钟仍然没有思路，再由家长进行提示性讲解。

讲解思路：

这道题属于排列组合问题，难点在于9条边围成了一个圈，自然想到将问题简化，考虑边没有围成一个圈的情况。

用a(n)表示n边形染3种颜色的方法数，我们将采用递推的方法解题

总的解题思路是：先计算9条边没有围成一个圈的情况，然后得到a(9)和a(8)的关系，接着计算a(3)的值，最后通过递推得到a(9)的值。

步骤1：先思考第一个问题，如果只有相连的9条边且没有围成一个圈，要求相邻2条边颜色不同，在3种不同的颜色下有多少种染色方法？

这个问题比较简单，从左到右逐渐染色即可，第一条边有3种选择，第二条边只有2种选择，此后所有边都只有2种选择，因此不同的染色方法数是3*2*2*…*2=768种。(注：其中有8个2相乘。)

步骤2：再思考第二个问题，a(9)和a(8)有什么关系？

对步骤1中的情况进行讨论，考虑第1条边和第9条边的关系，按颜色相同与否来划分：

第一种情况，如果它们颜色相同，则可以直接把这2条边再连成圈，此时对应的染色方法数就是a(9);

第二种情况，如果它们颜色不同，则此时第8条边与第1条边颜色不同，如果去掉第9条边，把前8条边连成一个圈，此时对应的染色方法数就是a(8),故a(9)与a(8)的和就是步骤1的结论，因此a(9)+a(8)=768。

步骤3：综合上述几个问题，考虑原题目的答案。类似于步骤2的过程可得：a(3)+a(4)=3*(2^3)=24,a(4)+a(5)=3*(2^4)=48,a(5)+a(6)=3*(2^5)=96,a(6)+a(7)=3*(2^6)=192,a(7)+a(8)=3*(2^7)=384,a(8)+a(9)=3*(2^8)=768。(注：2^3表示2的3次方。)

下面我们先计算a(3)的值，相当于三角形用3种颜色染色，不同的方法数是a(3)=3*2*1=6。代入第一个等式可得a(4)=18,然后不断代入其它等式递推，最后可得a(9)=510。所以共有510种不同的染色方法。

注：高中生对数列熟悉以后，可以得到a(n)=2^n+2*[(-1)^n],感兴趣的朋友可以自行推导。

思考题（3星难度）：6个小朋友围成一个圆圈玩游戏，有多少种不同的排队方法？