数学家们是怎么玩趣味拼图游戏的？
2020/12/9 17:00:00 中国科普博览
不变量理论是数学家在研究过程中很常用的一个分析手段。在实际问题中确定和寻找不变量以及可能的使用方法可以被看做为一门艺术，下面我们就从几个小小的趣味问题入手，带大家看看不变量的巨大作用。
数学史的渊源很深厚。追溯到4000多年前，我们在古巴比伦数学家的著作中就已经可以看出代数的痕迹了。根据相关历史，我们可以确认，以那时的知识甚至可以求解经典的二次方程。
巴比伦泥板显示了2的平方根的近似值，来源 Wikimedia
从那时起，数学就一直蓬勃发展，数学家们创造出了许多有用的数学工具。这里数学家们所谓的“数学工具”是指用来构建数学逻辑的方法或者技术。之后，数学家们将这些数学逻辑合并为独立的引理，之后又将引理转化为定理。
也许，我们并不能列举出数学中所有的逻辑和方法，但一些比较流行的方法还是可以举出的，比如数学归纳法和反证法，大学一般都会普及这两种方法。在这篇文章中，将会介绍另一种方法，这种方法很少被明显地提及，但是却足够解决实际问题。
Part. 1
引入不变量
假设有一个数学对象x和一组变换T (变换代表对 x 进行某些操作)，我们可以取集合T中的任何元素(即一个变换操作)并将其应用于x，来改变x的状态。这样，我们就可以形成x的不同态的链。
态的链
在这些概念的基础上，我们的主角，函数I登场了。函数I可以代表x的任意状态，比如说：它可以输出任意自然数或者有理数集。对于不同的x，检查I输出结果是否相等是很重要的一件事。
现在，如果能证明将变换T作用到x上，函数I不改变它的值，则可以用这个事实来证明逻辑语句，并将I称为由变换集T产生的对象x的不变量。
对于任何状态链x，不变函数的值不变
让我们考虑下面的示例，看看如何利用不变量来证明逻辑语句。
Part. 2
假想的群岛
我们将从一个简单的示例开始，然后尝试缓慢地增加复杂性。
假设我们是生活在群岛中某一片岛屿上的人。我们需要知道，如果没有任何一个桥梁跟我们的出发点连接，我们就无法到达特定的岛。
我们的虚拟小世界 图源 Wikimedia
我们能在自己所在的岛屿自由移动，但是桥梁只连接有限的岛屿，因此从一个岛屿不能到达所有的岛屿。
我们先将所有的岛标号并用数字连接。
数字代表岛屿跟桥梁 (i为岛屿，b为桥梁)
在上面的基础上，引入不变函数I，将我们所在的岛屿编号输入这个函数中，输出的结果就是我们可能会到达的岛屿编号。
将岛屿和桥梁映射成数字后的世界示意图
通过以上的示意图，将I可能的输出列举出来为：
不变函数I的值
很明显，在每个通过桥梁连接的“世界”中，我们任意沿桥梁移动并不会改变函数。那么，一个人是否能够从岛屿a到岛屿b？这个可以根据具体的函数I来决定。
根据函数I回答岛屿是否可达的问题
这就是关于不变量的一个例子，我们用它展示不变量的主要思想，接下来我们可以讨论一些更有意思的例子。
Part. 3
象棋问题
假设我们有一个棋盘，这个棋盘有些不同——有人从同一对角线上的角落里取下两个格点。
奇特的棋盘
假想出这个棋盘的人同时给出了一个挑战，并承诺挑战成功的人能够得到1万块：用2×1的多米诺骨牌填满这个棋盘。
乍一看，这个问题似乎很简单。从64个单元中去掉了偶数个格点，再拼放双数单元的多米诺骨牌并不难。搞明白这个之后，我们可能会毫不犹豫地接受这个挑战，毕竟，谁不想要1万块呢？
随机填充的结果
笔者根据这个规则制作了这个游戏的网页版本，这样我们就可以找到并证明这种可能性的存在。在网页版本游戏中请用鼠标左键放置多米诺骨牌，用鼠标右键改变多米诺骨牌的方向。
或者简单一点，建议各位拿出纸笔，尝试挑战一下自己。
在一段时间的尝试之后，我们可能会怀疑这种做法的可行性。下面让我们利用不变量的想法来剖析这个问题。
首先，定义不变函数I为棋盘中未填充部分黑色和白色单元格数量的差异，这个函数的初始值为0，当从棋盘上移除两个同样颜色的格点后，值变为2。
其次，我们发现，任意放置一个多米诺骨牌总会覆盖一个黑色和一个白色的单元格，所以无论放置多少个多米诺骨牌都不会改变之前定义的I值。
在放置多米诺骨牌时不变函数不会改变其值
现在可以看出其中的矛盾之处了么？全覆盖棋盘的I值应该为0，但是现在无论放置多少多米诺骨牌，I值都为2，不可能达到0.
哲学家马克斯·布莱克在1946年出版的《批判思维》一书中提出了这个问题。
Part. 4
15格点的拼图
19世纪末，山姆·洛伊德提出了另一个非常著名的谜题。作为一位美国象棋选手，他向世界发起挑战，要人们来解决他的15个格点的拼图问题(15 puzzle)。
15格点的拼图游戏
15个格点的拼图游戏本身是个智力趣味题，需要在棋盘上移动棋子使之按照1到15的顺序回归初始位置，这个的在线玩法也很容易找到。这个谜题在山姆·洛伊德提出的十年前就被提出了，但是，当洛伊德提出要提供1000美元作为奖金给解出15拼图之后，这个游戏才迅速在世界上传播开来。
山姆·洛伊德最后两块交换后的拼图，图源Wikimedia
山姆·洛伊德的版本有所不同，他从初始版本的拼图开始，把14和15互换了位置。最终目的是一样的：通过某种变换将其顺序恢复到初始情况。
如何利用不变量来解决这个问题？我们来看一下。
我们先将拼图排成一条直线。
将拼图变成一条直线
接下来我们将每个单元格编号：
将原始拼图中格点的移动映射到这条线上点的重排。
将拼图中的移动映射到线上
对于这条线，我们可以计算逆序数，逆序数指的是：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。(比如说：1 2 3 的逆序数为0，1 3 2的逆序数为1，3 1 2的逆序数为 2。)
对于从1到15的每个值v，我们应该计算从具有该值v的单元的位置i开始向右开始有多少个值小于v。
一个格点的逆序数，Ind 代表如果括号里面是真的话输出为1，反之则为0
计算所有格点的逆序数之和，得逆序数的和为：
逆序数之和
现在，我们来变个魔术。对于将全部的逆序数和空格点所在的行数相加所得的和总是偶数，这样可以定义不变函数I。如果总和为偶数，I则为0，和为奇数，I为1。
在移动中，不变量保持不变
在这篇文章中可以找到不变量不变的严格解，其利用了置换的理论来证明。
经过以上分析，可以看出山姆·洛伊德的15拼图中的不合理之处：如果交换相邻的两个格点而不改变空格点初始位置，逆序数将会增加1，因此I总会是奇数。这件事告诉我们，利用一般的方法是没有办法将拼图恢复到原来的位置的。
(当然，还有非常规的方法，具体可参见这里)
Part. 5
我们能更进一步吗？
不变量的应用不仅仅局限于拼图中。在现代数学中可以找到这种方法的很多应用：复分析、微分方程和其他理论。在实际问题中确定和寻找不变量以及可能的使用方法可以被看做为一门艺术，也许，这也是数学家们爱上这门学科的原因吧。
最后，希望这个故事可以让更多人对数学更好奇一些，更深入一些。
文章来源：中科院物理所本文仅代表作者观点，不代表中国科普博览立场
转载注明出处 未经授权不得转载转载授权、合作、投稿事宜，联系webmaster@kepu.net.cn
中国科普博览是中科院科普云平台，由中科院计算机网络信息中心主办，依托中科院高端科学资源，致力于传播前沿科学知识，提供趣味科教服务。
点这里告诉我你在看
源网页 http://weixin.100md.com
返回 中国科普博览 返回首页 返回百拇医药