发信人: eigolomoh(异调)
整理人: k_xiaoyao(2001-06-13 00:45:32), 站内信件
|
北京版上有网友出了道数学题，我借题发挥了一下，写得那么辛苦
也在这里帖一下吧。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
主题：一道数学题，很有意思，来试试吧！
作 者: lighu(大师) 2001-05-10 07:36:44 :0 :0
[回复] [打包] [转贴] [修改] [删除] [标记保留] [加至精华区]
玩过拼图游戏吧，六个方格。是否能完成一个转换！
|--|--|--| |--|--|--|
|A |C |E | |A |D |E |
把 |--|--|--|通过移动方格，转化成为 |--|--|--|
|B |D | | |B |C | |
|--|--|--| |--|--|--|
条件所限，只能画个简图
--
作者：lighu【大师】
----------------------------------------------------
这个题其实是4*4情况的简化形式（那个游戏是不是叫“梁山英雄排
座次”？）。
解决这个题要用到数学里一种经典而巧妙的方法，就是不变量方法。
数学研究有一大项工作，就是要把所研究的数学对象分类（分类可以
说是绝大多数科学中最重要的工作之一，学生物的朋友听了我这话一
定会把头点得跟鸡啄米一样:-)）。比如我们有时候听到的等价、同态、
同构、同胚、同伦这些数学名词，都是研究某些数学对象在特定的变
换下可以变换为另一些数学对象，如果两个数学对象可以这么互相变
来变去，我们就把它们归成一类。
问题在于，如果要考虑所有这些特定的变换，工作量太大，有时候还
不可能，因为所需要的计算太复杂，更常见的是根本没办法计算，因
为所考虑的对象和变换都是以抽象的形式定义出来的。这里我们就要
使用不变量方法了。简单地说，不变量方法就是考查一些数学对象中
的某些特征，这些特征相对来说比较容易描述或计算。尤其重要的是，
这些特征在我们要研究的特别的变换中不会改变，于是如果我们遇到
两个数学对象具有不同的这类特征，我们就可以断定，我们不可能用
我们正在研究的变换把一个对象变为另一个对象。
举个例子，我们想象橡皮膜做的一个球面和一个轮胎面。我们问，在
不撕裂和不粘合橡皮膜，但是允许随意拉伸和扭曲橡皮膜的情况下，
能不能把球面变到轮胎面或者把轮胎面变到球面？考虑所有可能的拉
伸和扭曲显然是不现实的，但是我们有一个很巧妙的办法。我们知道
在不撕裂和不粘合橡皮膜的情况下，无论怎么拉伸和扭曲，曲面上的
“洞”的数目是不会改变的，现在球面上没有洞（也就是有０个洞），
而轮胎面上却有１个洞。所以我们立刻可以得出结论说，在上面所说
的变换下，球面和轮胎面之间的互相转化是不可能的。这里曲面上的
“洞”的个数就是我们所说的不变量，在拓朴学里把它叫做这个曲面
的“亏格”。
上面所说的当然是比较简单的例子，许多有用的不变量隐藏得非常深，
需要数学家辛勤的工作才能把它们找出来，成为数学家的强大工具。
陈省身先生最伟大的贡献，就是发现了微分几何中“陈氏示性类”这
种不变量。现在有关流形（就是曲线曲面更高维数的推广）分类的研
究，几乎不可能不和它打交道。
好了，说了半天该解决我们的问题了。要列举所有的转换，然后断定
可能还是不可能，虽然不是不可行，但是毕竟太麻烦。我们要用不变
量的技巧来解决这个问题。我把图改写一下，用数字来表示每一块：
1 2 3
4 5
能不能通过向唯一的空格移动上下左右中的一块这种方法来把上面的
图形变为
1 5 3
4 2
我们把这些数字写成一排，略去空格，第一个图就是
1 2 3 4 5
而第二个图是
1 5 3 4 2
我们可以从一个序列中随意取两个数字，但是保持它们的顺序，比如
说在第二个序列中我取第一和第五个数，那么就得到一对数字(1,2)，
这一对数字中第一个比第二个小，我们称这对数是“顺序”的。但是
如果我们取第二和第四个数得到的这对数(5,4)，就是第一个比第二个
大，我们称这对数是“逆序”的。我们定义上面这样一个序列中的
“逆序数”是这个序列中所有逆序对的个数。
比如说第一个序列，因为所有数字都是从小到大排列的，所以自然它
的逆序数是0。而第二个序列中，我们可以列举出所有逆序对：
(5,3) (5,4) (5,2) (3,2) (4,2)
所以它的逆序数是5。
我们现在考查向空格中移动方块会怎样改变逆序数。显然水平的左右
移动不会改变逆序数。现在如果排列是
a b c
d e
我们把b向下移动，使图形变为
a c
d b e
那么序列就从
a b c d e
变为
a c d b e
我们看到所有有a或e在内的数对都没有改变，因为所有原来在a后面
的数现在还在a后面，而所有原来在e前面的数现在还在e前面。改变
了的数对是(b,c)和(b,d)，现在变成(c,b)和(d,b)了。想一想很容易
知道，在这样的情况下，序列的逆序数有可能会变化，但是变化量只
能是-2,0或2，也就是说，逆序数的奇偶性是不变的。所以在允许的
移动方式下，逆序数的奇偶性是个不变量。
这下简单了，我们上面的两个序列的逆序数一个是0，一个是5，所以
逆序数的奇偶性不同，所以是不可能从一种图形变到另一种图形的。
当然，如果奇偶性相同，那并不表明就一定可以互相转换，是否真如
此，这个问题需要更多的研究和证明。不过那就是另一个问题了:-)
4*4的情况和这类似，只不过更复杂一点，而且不变量也不能取作逆
序数的奇偶性了，而是要取作逆序数被3除的余数。 |
|