第23讲 不变量原理.doc

第23讲 不变量原理有一句容易记住的话：如果有重复，寻找不改变的东西！ A恩格尔大千世界在不断地变化着，既有质的变化，更有量的变化。俗话说：“万变不离其宗”。在纷乱多样的变化中，往往隐藏着某种规律，这就需要我们透过表面现象，找出事物变化中保持不变的规律，从“万变”中揭示出“不变”的数量关系。寻求某种不变性，在科学上称之为守恒，在数学上就是不变量。从某种意义上说，现代数学就是研究各种不变量的科学。20世纪最重大的数学成就之一阿蒂亚-辛格(Atiyah-Singer)指标定理，就是描述某些算子的指标不变量。影响遍及整个数学的陈省身示性类（Chern class），正是刻画许多流形特征的不变量。一些代数不变量、几何不变量、拓扑不变量的发现，往往是一门学科的开端。经典例题解析让我们通过一个简单例子来揭示不变量原理。例1 在某部落的语言中一共只有两个字母：和，并且该语言具有以下性质：如果从单词中删去相连的字母，则词义保持不变。或者说：如果在单词中的任何位置增添字母组合或，则词义不变。试问，能否断言单词与词义相同？解 应当注意：在保持词义不变的各种增或删的变化之中，与总是增删同样的个数。因此这些变化不会改变单词中两种字母的个数之差。例如在如下一串“保义变化”中始终比多一个： 。回到原来的问题：在单词中，比多一个；而在单词中，却比少一个！因此我们不能断言：这两个单词同义。上述解答用实例说明了不变量原理运用的主要思路。我们面对某些对象，对于它们可以进行一定类型的操作，在操作之后便提出了这样的问题：能否由一种对象变为另一种对象？为了回答这个问题，我们构造出某种量，这种量在所作的操作之下保持不变。如果这种量对于所言的两个对象是不同的，那么便可给予所问的问题以否定的回答。例2 10名乒乓球运动员参加循环赛,每两名运动员之间都要进行比赛.在循环赛过程中,1号运动员获胜x1次,失败y1次;2号运动员获胜x2次,失败y2次,等等.求证:x12+x22+x102=y12+y22+y102.证明 每个运动员共比赛9场,其获胜与失败总数和为9,即xi+yi=9(1=i=10).既然每场比赛一些运动员获胜,另一些运动员要失败,那么x1+x2+x10=y1+y2+y10,从而 (x12+x22+x102)-(y12+y22+y102) = (x12-y12)+(x102-y102)= 9(x1+x2+x10)-(y1+y2+y10) = 0所以 x12+x22+x102=y12+y22+y102.例3 从数组出发，每一步可以选其中两个数，并把它们换成以及。问：是否能在有限步后达到目标？ 解 由于，故经过多次替换后所得3个数的平方和是一个不变量：而由于这目标不能达到。目标不能达到。评注 这里的不变量是点到点的距离，即点总在以为中心，半径为13的球面上，而由于目标在以为中心半径为14的球面上，这目标不能达到。1. 不变量奇偶性例4 一个圆分为6个扇形（图115）。每个扇形中放有一枚棋子。每一步允许将任何两枚棋子分别移入相邻的扇形。试问，能否通过这种操作，把6枚棋子全都移到一个扇形之中？ 图115 图116 图117 解 将6个扇形依次编为1至6号（图116）。对于棋子的任何一种分布，我们考察6枚棋子所在扇形的号码之和。例如，在如图117所示的分布中，我们有。显然，在把一枚棋子移到相邻的扇形中后，它在中的那一项的奇偶性发生了变化。这也就是说，如果同时移动两枚棋子，那么的奇偶性保持不变这是一个不变量！但是一开始时（图115），我们有，为奇数。而如果所有6枚棋子全都在一个扇形之中，则当该扇形编号为时，就有，都为偶数。所以我们不可能通过所述的移动，把棋子的分布从原来的分布变为全在一个扇形中。点评 由于奇偶性是整数的固有属性，因此可以说奇偶性是一个整数的不变性，对于某些问题，找出了不变性就找出了解答。比如，例3通过考察和的奇偶性不变，使问题得以顺利解决。2. 不变量余数例5 某海岛上生活着45条变色龙，其中有13条灰色的，15条褐色和17条紫色的。每当两条颜色不同的变色龙相遇时，它们就一起都变为第三种颜色（例如，灰色和褐色相遇，就都变为紫色）。能否经过一段时间，45条变色龙全都变为同一颜色？解 每一次变化，都有两条不同颜色的变色龙消失，并随之而“诞生”两条第三种颜色的变色龙。我们用数组表示变色龙的状况，其中分别表示灰色、褐色和紫色变色龙的数目。于是由题意知，在一次变化之后，或变为，或变为，或变为。我们发现，灰色和褐色变色龙的数目之差的变化只能为和。这就是说：该差被3除的余数保持不变，这是一个不变量。在开始时，有。而如果全都变为同一颜色，则必。故为不可能。例6 有3部卡片打印机。第一部能根据原有卡片上的号码，打印一张号码为的卡片；第二部则当原号码中二数皆为偶数时，打印一张号码为的卡片；第三部根据两张号码分别为和的卡片，打印一张号码为的卡片。打印过后，原有卡片和新卡片全都归顾客所得。试问，能否利用这3部打印机，由一张卡片为的卡片得到号码为的卡片？解 从题目的外形看，给定了允许的操作方式内容，要求我们回答：能否从一种卡片出发得到另一种卡片这就提醒我们，应当找到不变量。就让我们开始找吧！第一种操作：。在这种操作之下，什么东西未加改变呢？那么当然是卡片上的两个号码之差：。但是在第二种操作之下，这种号码差却是变化的：减半。而第三种操作使得两张卡片上的号码差相加：。这种状况使我们看到：号码差并非不变量。那么，究竟什么是不变量呢？看来我们一时难以找到。还是让我们来仔细观察一下吧。先来碰碰运气，看看从我们的卡片可以得到一些什么样的卡片吧！暂时到此为止。我们来看看我们的劳动果实吧！我们现在有一组卡片，算一算它们之上的号码差，得：14，14，7，7，21。由此立即可以猜出我们所要证明的结论，这就是：号码差应当恒为7的倍数。其证明十分简单，只要再次回顾一下三种操作之下，号码差的变化规律即可（见上面的讨论）。现在注意到，在卡片上，这个号码差却为，它不是7的倍数。可见我们得不到这样的卡片。毫无疑问，在运用不变量解题时，最重要的是找出“不变量”。这是一门真正的艺术，要想掌握它，必须在解答类似的题目中积累经验。在这里光靠猜是不行的，并且应当记住：（1） 所找出的量应当是不变量；（2） 这种不变量对于题中的两类对象应当取不同的值；（3） 应当立即确定下来我们的不变量所要反映的对象的类型。3. 染色大量用不变量来解的问题需要借助一种专门形式的不变量即所谓“染色”。下面是一个典型例子：例7 棋子“骆驼”在的棋盘上走步，即往横向走一格再往纵向走三格（横1纵3），也可纵1横3。（有点象“马”，不过“马”是走步）。试问，“骆驼”可否经过几次跳动到达某个与原来相邻的方格？解 不可能。设想棋盘已如国际象棋棋盘那样黑白相间地染了颜色。容易看出，“骆驼”一定是在颜色相同的格子之间跳动。这就是说：格子的颜色是一个不变量。由于相邻的格子的颜色必不相同，所以“骆驼”不可能跳入其中。4. 半不变量单调变化的量“半不变量”的思想极其自然地延续了不变量的思想。所谓“半不变量”是指在变换过程中单调变化的量，亦即仅增大或仅减小。典型的半不变量的例子有：人的年龄，它仅能随着时间的流逝而增大。例8 在十个容器中分别装有1,2,3,4,5,6,7,8,9,10毫升的水.每次操作可由盛水多的甲容器向盛水少的乙容器注水, 注水量恰好等于乙容器原有的水量. 问:能否在若干次操作后，使得5个容器都装有3毫升的水, 而其余容器分别装有6,7,8,9,10毫升的水? 如果能,请说明操作程序; 如果不能,请说明理由.解 不能设甲容器水量为，乙容器水量为，转注前后两容器水量和相等，所以转注前转注后甲容器乙容器甲容器乙容器a + b = (a-b) + 2b奇奇偶偶奇偶奇偶偶偶偶偶偶奇奇偶从以上可见，每次操作后，水量为奇数的容器数目不增由于初始状态有五个杯中水量是奇数毫升，因此无论多少次操作，水量为奇数毫升的容器数总不能比5多，所以5个容器有3毫升水，其余容器分别装有6，7，8，9，10毫升水（总计有7个容器水量为奇数毫升）的状态不可能出现.同步训练1 给定一个三元数组。对于其中任何二数可进行如下操作：如果这两个数是与，那么就把它们变为与。试问，能否通过这种操作，由三元数组出发，得到三元数组？2一条龙有100个头。一名武士一剑可以砍掉它的15，17，20或5个头，就在这四种情况下，在龙的肩上又分别会长出24，2，14或17个新的头。如果把头都砍光时，龙就死了。龙会死吗？3从到的每一个数反复地被换成该数所有数字的和，直到得到个一位数。这些数中1多还是2多？4设是的所有数字的和，解方程：。5在图1.1中，有公共边的两个方格称为相邻的。考虑下面的运算：取任意两个相邻的数并加上同一个整数。能够把图1.1经若干次迭代变成图1.2吗？ 图1.1 图1.2 图26证明：的国际象棋盘不可能划分为15个的矩形和1个如图120所示的图形。 7. 在的棋盘的每个方格中有一个整数。每次可取一个或的正方形，并把其中的每个数都加上1。是否总能得到一个数表，使得表中每个数都是偶数；表中每个数都是3的倍数？8.对于二次多项式，允许做下面的运算：把和对换；把换成，其中是任何实数。重复做这样的运算，能把变成吗？9如果多项式和分别是用加，减，乘是否能从和得到？10在一个的方块中，九个方格被感染了。在单位时间后，只要是某个未感染的格子与两个已感染的格子相邻，这个格子也被感染。问感染是否能传播到每个格子？11. 12名矮人住在森林里，每人将自己的房子染成红色或白色在每年的第i月，第i个矮子访问他所有的朋友（这12个矮人中的）如果他发现大多数朋友的房子与自己颜色不同，那么他就将自己房子的颜色改变，与大多数朋友的保持一致证明：不久以后，这些矮人就不需要改变颜色了12在正12边形的一个顶点上写着-1，其余顶点上都写着1。允许同时改变任何连续个顶点上的数的符号。试问，能否通过这样的操作，使得惟一的-1移到与原来位置相邻的顶点之上，如果13 沿着圆周放着一些实数。如果相连的4个数满足不等式，那么我们就可以交换与的位置。证明：这种交换至多可进行有限次。14 某班有47个学生，所用教室有6排，每排有8个座位，用 (i, j) 表示位于第i排第j列的座位。新学期准备调整座位，设一个学生原来的座位为(i, j)，如果调整后的座位为(m, n), 则称该生作了移动 a, b=i-m, j-n, 并称a+b为该生的位置数，所有学生的位置数之和记为S求S的最大可能值与最小可能值之差同步训练参考答案1不能。考察数组中3个数的平方和。2头的个数模3不变，开始时为1，永远如此。3考虑模9的余数，这是个不变量。因为,1的个数比2的个数多1。4变换使被3除的余数不变，从而把方程模3有形式。无解。5把方格如图1交替地染成黑色和白色。设和分别是白格和黑格中数的和。用操作时是不改变差。对图1.1和1.2，差分别是5和1。从5不能得到1。 图16对方格表用两种颜色染色，每一行染为同一种颜色，行与行则两种颜色交换。7. 设是除第三、六行外的所有数的和。如果开始时，棋盘上总会有奇数。 设是除第四、八行外所有的数的和，则是个不变量。如果开始时，则棋盘上总有数不被3整除。评注 模n的余数是一种常见而重要的不变量。8我们考虑判别式。第一种运算显然不改变。第二种运算不改变多项式的根的差。现有，而，从而。也就是说第二种运算不改变。由于两个三项式的判别式是9和5，目标不能达到。9对用这三种运算，我们得到多项式， （1）它应该对任何成立，对和，我们给出特定的的值，使（1）不正确。在中，在对6反复用三种运算时，总是得到6的倍数，但（1）的右边是2。在中，（1）的左边是个整数，而右边是个分数。在中能够找到和的多项式，使它等于：。10考虑有2个，3个或4个被感染邻居的健康格子。可以看到被感染区域的周界是不会增加的（但可以减少）。开始时，受感染区域的周界至多是。所以目标是不会达到的。11. 将12名矮子当作12个点，如果两名矮子是好朋友，就在相应的两点之间连一条线，并且在他们的房子颜色相同时，这条线为蓝色；不同时，为黑色考虑蓝色线的总数S一方面，S是有限数；另一方面，每名矮子变更颜色时，S严格增加（至少增加1）因此，在有限次变更后，这些矮子就不需要变更颜色了12对于每一种情形，我们答案都是否定的，而且证明的思路相同。我们涂黑其中一部分顶点，使得任何连续的个顶点中都有偶数个被涂黑的顶点（图3）。图2我们可把黑色顶点上所写的所有数的乘积作为不变量（因为每次操作都改变其中偶数个数的符号，因之乘积不变）。但是该乘积在开始时为-1，而如果-1移到了与原来相邻的左边顶点上，那么该乘积就是1，所以不可能。评注 上述解答中体现了“不变量”方法中的扩散思路：从每个对象中分出一部分来，使得所作操作在这部分中所带来的变化看起来特别简单。13考察圆周上所有相邻