关于十五子的游戏

陈景润，1933年5月22日生于福建闽侯．他家境贫寒，但学习刻苦.他在中、小学读书时，就对数学情有独钟，一有时间就演算习题，在学校里成了个“小数学迷”．他不善言辞，为人真诚和善，从不计较个人得失，把毕生精力都献给了数学事业．高中没毕业就以同等学力考入厦门大学．1953年毕业于厦门大学数学系．1957年进入中国科学院数学研究所并在华罗庚教授指导下从事数论方面的研究．历任中国科学院数学研究所研究员、学术委员会委员兼贵阳民族学院、河南大学、青岛大学、华中工学院、福建师范大学等校教授，原国家科委数学学科组成员，《数学季刊》主编等职．主要从事解析数论方面的研究，并在哥德巴赫猜想研究方面取得国际领先的成果．这一成果被国际上誉为“陈氏定理”，受到广泛引用．

我们先来介绍一点组合数学的知识，有一堆东西，需要把它们排列出来，我们可以给每一个东西编一个号，例如按某种规定依次编为1，2，…，n.我们称这个从小到大的序列（1，2，…，n）为顺序列，但若出现一个大的数排在小的数的前面，例如（1，3，2，4，…，n），这是一个在顺序上发生杂乱的序列，我们不妨称之为非顺序列.人们规定：若在一个序列中，有一个数排在比它还要小的另一个数之前，我们称之为一个倒置.例如非顺序列（1，3，2，4，5）有一个倒置，又如（3，1，2，4，5）有两个倒置，因为3不仅在2之前，而且还排在1之前，再如（3，2，1，4，5）有三个倒置，因为3排在1，2的前面，这有两个倒置，2排在1的前面，又有一个倒置.我们称顺序列的倒置为0 ，这是因为顺序列没有发生倒置.根据倒置数的不同，我们可以把所有的序列分成两类，一类是倒置数为偶数的序列，我们称它为偶置序列（顺序列也应归为倒置序列）；另一类是倒置数为奇数的序列，我们称它为奇置序列.

设图1是一个十五子游戏的初始位置，我们先把这15个数排成一个序列：5，1，4，3，10，8，2，13，6，9，14，12，7，15，

11.其中5排在最前面，因而有1，2，3，4这四个比它小的数排在它后面，所以仅仅对5来讲，有4个倒置，我们把4写在横线下和5对应；1排在第2，虽然5排在它前面，但这一个倒置在计算5的倒置数时已经算过了，所以不再计算.而1的后面再也没有比1小的数了，因而1的倒置数是0，把0记在1的下面；同理，在4的后面而比4小的数有3和2两个，因而4的下面记下2；依此类推，得图2.

的），事实上，要判断其是奇置序列还是偶置序列，用不着把这些倒置数加起来.因为偶数加偶数还是偶数，奇数加偶数还是奇数，就是说，一个整数加上一个偶数并不改变原来这个整数的奇偶性，因此我们只需要数一下倒置数中有多少个奇数，若是偶数个奇数，则这个序列是一个偶置序列；若有奇数个奇数，则这个序列一定是个奇置序列.图2下面的一行数中共有1，5，3，5，1，3，1七个奇数，故马上断定图上的序列是一个奇置序列.

下面我们来研究一下，一个序列中相邻的两个数调换一下位置，倒置数会发生什么变化.例如一个序列中某一对相邻的两数为x，y，当两数调换位置后，变为y，x .若x大于y，则x，y的顺序是不正常的，即有一个倒置，现在变为y，x，即小的在前，大的在后，因而原来的一个倒置消失了；若x小于y ，则x，y这两个数之间没有倒置，变为y，x后，小的在后，大的在前，因而产生了一个倒置.因此，我们可以断言，两个相邻的数若调换位置后，序列倒置数的奇偶性一定发生改变.若有三个相邻的数x，y，z，把x调到z的后面，变为y，z，x，这时候我们可以把这样的调换，先看为是x与y变换位置，变为y，x，z，再把x与z变换位置，变为y，z，x，即经过了两次相邻的调换，因而原序列倒置数的奇偶性要发生两次变化，即奇—偶—奇，或者是偶—奇—偶，这样，一个数在序列里向前跳过两个数或向后跳过两个数后，序列的奇偶性不变.若是四个相邻的数排成为x，y，z，w，当x调到w之后，变为y，z，w，x时，显然还可以把这个变换分成为三个相邻的变换，即x先与y变换，再与z交换，最后与w交换，因而原序列倒置数的奇偶性也经过三次变换，即奇—偶—奇—偶或偶—奇—偶—奇，故序列的奇偶性要变.

在十五子游戏中，我们的变化不过是把空格向左右或向上下移动，当空格向左右移动时，原位置的序列没有发生变化，例如在某一行中，原来的位置是xyz，当空格向右移动时变为xyz，空格向左移动时变为xyz，这两种情况的序列都是“xyz”，因而我们断言，当空格向左右移动时，原序列的例置数不变，所以倒置数的奇偶性没有发生变化.当空格向上移动时，例如由图3变为图4，因为图3展开的序列为（**xyzw*），而图4展开的序列为（**yzwx*），即*向后跳了三个位置，因而按前面的分析，序列的奇偶性要改变.同理当空格往下移动一格时，即由图4变为图3时，序列的奇偶性也要改变，而当空格向上移动一格后，又向右或者向左移动时，最后又向下移动到空格原来所在行时，则序列倒置数的奇偶性变化了两次，因而知道倒置数的奇偶性不变，若空格向上或向下移动两格，则序列倒置数的奇偶性也变化了两次，结果倒置数的奇偶性仍然不改变，但若向上或向下移动三次则奇偶性就要改变了.

在十五子游戏中，最后结果空格是在第四行，因而若空格原位置在第四行或者第二行，则到最后位置时，序列的奇偶性不会改变，若空格原来的位置是在第一行或第三行时，则最后位置的倒置数的奇偶性要发生变化.

我们在前面已经讲 过，不论十五子游戏的最初位置如何，最终总可以变为正常排列（偶置序列）或奇异排列（奇置序列）.因此，当原位置的序列是偶置序列，而空格在第一行或第三行时，它只能变为“奇异排列”；若空格在第二行或第四行，则一定可以变为正常排列.当原位置的序列是奇置序列，而空格在第一行或第三行时，则最终总可以变为“正常排列”；当空格在第二行或第四行时，它就只能变为“奇异排列”了.由于“正常排列”与“奇异排列”的空格都在第四行，因而“正常排列”（偶置序列）再经过任何移动也不可能变为“奇异排列”（奇置序列）.

到此，我们就完全掌握十五子游戏的奥秘了.因为我们不但能把它排成最终状况，而且能预先就知道它能不能排成“正常排列”，这只须简单计算一下序列倒置数的奇偶性，再看一下空格在第几行就行了.就这样，我们仅仅使用了一点点数学概念就把神秘的十五子游戏变得十分简单明了了.

顺便指出，任何n2个纵横数相同的小方格和n2 - 1个小纸板都可以玩“n2 - 1子游戏”，例如纵横各五的25个小方格和24个小纸板的“二十四子游戏”，与十五子游戏一样，可以总结出规律，并且规律更简单一些，这里我们就不再介绍了.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文