环状涂色问题的优化教学

1、问题的背景：问题的背景： （2003年全国高考题）年全国高考题） 如图，一个地区分为如图，一个地区分为5个行政区域，现给地图着色，个行政区域，现给地图着色，要求相邻区域不得使用同一种颜色，现有可供选择，要求相邻区域不得使用同一种颜色，现有可供选择，则不同的着色方法有则不同的着色方法有_种。种。 12345 在一个正六边形的六个区域栽种观赏植物在一个正六边形的六个区域栽种观赏植物（如图）要求同一区域中种同一种植物，相邻的两块（如图）要求同一区域中种同一种植物，相邻的两块种不同的植物。现有种不同的植物。现有4种不同的植物可供选择，则栽种不同的植物可供选择，则栽种方案有种方案有 _种。种。 ABCD

2、EFP问题：问题：第一类：第一类：若若A、C、E所种植物都相同，则种所种植物都相同，则种A、C、E有有4 种方法，种种方法，种B、D、F各有各有 3 种方法，所以完成种植种方法，所以完成种植有有4333=108 种方法。种方法。 第二类：第二类：若若A、C、E所种植物两两不同，则种所种植物两两不同，则种A、C、E 有有4 3 2种方法，种种方法，种B、D、F各有各有2种方法，所以完成种方法，所以完成 种植有种植有4 3 2 2 2 2=192种方法。种方法。对对A、C、E 所种植物是否相同分为三类：所种植物是否相同分为三类：第三类：第三类：若若A、C、E所种植物仅有两区域一样。所种植物仅有两区

3、域一样。若若A与与C同，则种同，则种A、C、E有有4 3种方法，种种方法，种B、D、F分别有分别有3、2、2种方法，故有种方法，故有4 3 3 2 2=144种方法。种方法。若若A与与E同，同理可得，有同，同理可得，有144种方法。种方法。 若若C与与E同，亦同理可得，有同，亦同理可得，有144种方法。种方法。 将上述三大类结果相加，得所求种植方法数为将上述三大类结果相加，得所求种植方法数为732种。种。 （更巧解）（更巧解）作圆被分成了作圆被分成了3、4、5、6个扇形区域的图形个扇形区域的图形,如下：如下： （图（图A）（图（图B）（图（图C） （图（图D） 对图对图A，按要求显然有，按要求

4、显然有4 3 2=24种栽种方案。种栽种方案。对图对图B，用去杂法求解，假设，用去杂法求解，假设4区域种法依次为区域种法依次为4、3、3、3种种， 则需减去首尾两区域种相同植物的情形（相当于图则需减去首尾两区域种相同植物的情形（相当于图A的情形）的情形） 故有故有 种栽种方案。种栽种方案。 34 32484 对图对图C，类似于图，类似于图B的解法，假设的解法，假设5个区域种法依次为个区域种法依次为4、3、3、3、3种，则需减去首尾两区域种相同植物的情形（相当于种，则需减去首尾两区域种相同植物的情形（相当于图图B的情形）。的情形）。 故有故有44 384240 种栽种方案。种栽种方案。（图（图A

5、）（图（图B）（图（图C） （图（图D） 对图对图D，类似于图，类似于图C的解法，假设的解法，假设6区域种法依次为区域种法依次为4、3、3、3、3、3种，则需减去首尾两区域种相同植物的情形（相当于种，则需减去首尾两区域种相同植物的情形（相当于图图C的情形）。的情形）。 种栽种方案。种栽种方案。 故有故有 732240345问题：问题： 记为记为相连构成相连构成n个三角形，个三角形， 2MnM1M、，k(2)k 现取现取种颜色对这种颜色对这n个三角形涂色，每相邻的两个三角形的涂色不同，个三角形涂色，每相邻的两个三角形的涂色不同，试求涂色的方案有多少种？试求涂色的方案有多少种？ 如图，已知如图，已

6、知p是是n(n3)边形内的一点，它与边形内的一点，它与n个顶点个顶点 图2 M n M 6 M 5 M 4 M 3 M 2 M 1Pan) 2( n设涂法总数为设涂法总数为先对先对 2n 1M2M当当时，看作只有时，看作只有两个相邻区域，两个相邻区域， 与与1M涂色，有涂色，有 种涂法，继而对种涂法，继而对 k2M有有 1k种涂法，种涂法， 因而因而 ) 1(2kka下面导求当下面导求当 3n时，时， an的递推公式：的递推公式： 先对先对 1M涂色，有涂色，有 k种涂法，继而种涂法，继而 2M有有 1k种涂法，种涂法，这样，共有这样，共有 1( 1)nk k种涂法。种涂法。 1nM有有 1k

7、种涂法，种涂法， nM仍有仍有 1k种涂法，种涂法，而这些涂法可分为两类：而这些涂法可分为两类： 一类是一类是 nM与与 1M同色；同色； 另一类是另一类是 nM与与 1M不同色，不同色， 前者与要求不符，但可认为前者与要求不符，但可认为 nM与与 1M合为一个三角形，合为一个三角形， 此时，涂法有此时，涂法有 1na种。种。故得递推公式为：故得递推公式为： 11) 1(nnnkkaa) 3( n令令 1nnnkab) 1() 1)(1(1bbnnk 即即 111 ()(1)1nnkbb 2221111(1)()()111nnnkkkbb 211( 1) ()1nnk 则则 11nnkkb bnnnkka) 1() 1() 1(23n ( 1)11nnnkka 故故问题的评价：问题的评价：教学题材的创新是创新教学的源头活水。教学题材的创新是创新教学的源头活水。传统的题材对学生形成概念和巩固概念有着很好的效能。传统的题材对学生形成概念和巩固概念有着很好的效能。但一成不变的但一成不变的“单一思路单一思路”不能使青年学生广泛接受，不能使青年学生广泛接受，不利于学生形成对数学的正确的情感、态度和价值观，不利于学生形