关于十五子的游戏

陈景润

我们先来介绍一点组合数学的知识.有一堆东西，需要把它们排列出来，我们可以给每一个东西编一个号，例如按某种规定依次编为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 ，这是因为顺序列没有发生倒置.根据倒置数的不同，我们可以把所有的序列分成两类，一类是倒置数为偶数的序列，我们称之为偶置序列（顺序列也应归为偶置序列）；另一类是倒置数为奇数的序列，我们称之为奇置序列.

设图18是一个十五子游戏的初始位置，我们先把这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；依此类推，得图19.由于4+0+2+1+5+3+0+5+0+1+ 3+2+0+1+0= 27是一个奇数，因而这是一个奇置序列（请注意，这时我们是把空格抛开来计算的）.事实上，要判断其是奇置序列还是偶置序列，用不着把这些倒置数加起来.因为偶数加偶数还是偶数，奇数加偶数还是奇数，就是说，一个整数加上一个偶数并不改变原来这个整数的奇偶性，因此我们只需数一下倒置数中有多少个奇数，若是偶数个奇数，则这个序列是一个偶置序列；若有奇数个奇数，则这个序列一定是个奇置序列，图19的下面一行数中共有1，5，3，5，1，3，1七个奇数，故马上断定图上的序列是一个奇置序列.

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

在十五子游戏中，我们的变化不过是把空格向左右或向上下移动，当空格向左右移动时，原位置的序列没有发生变化，例如在某一行中，原来的位置是[xyz]，当空格向右移动时变为[xyz]，空格向左移动时变为[xyz]，这两种情况的排列都是xyz，因而我们断言，当空格向左右移动时，原序列的例置数不变，所以倒置数的奇偶性没有发生变化.当空格向上移动时，例如由图20变为图21，因为图20展开的序列为（**xyzw*），而图21展开的序列为（**yzwx*），即x向后跳了三个位置，因而按前面的分析，序列的奇偶性要改变.同理，当空格往下移动一格时，即由图21变为图20时，序列的奇偶性也要改变.而当空格向上移动一格后，又向右或者向左移动时，最后又向下移动到空格原来所在的行时，则序列倒置数的奇偶性变化了两次，因而知道倒置数的奇偶性不变.若空格向上或向下移动两格，则序列倒置数的奇偶性也变化了两次，结果倒置数的奇偶性仍然不改变，但若向上或向下移动三次则奇偶性就要改变了.在十五子游戏中，最后结果空格是在第四行，因而若空格原位置在第四行或者第二行，则到最后位置（即图16或图17）时，序列的奇偶性不会改变；若空格原来的位置是在第一行或第三行时，则最后位置的倒置数的奇偶性要发生变化.我们在前面已经讲过，不论十五子游戏的最初位置如何，最终总可以变为图16的正常排列（偶置序列）或图17的奇异排列（奇置序列）.因此，当原位置的序列是偶置序列，而空格在第一行或第三行时，它只能变为奇异排列；若空格在第二行或第四行，则一定可以变为正常排列.当原位置的序列是奇置序列，而空格在第一行或第三行时，则最终可以变为正常排列；当空格在第二行或第四行时，它就只能为奇异排列了.由于正常排列与奇异排列的空格都在第四行，因而正常排列（偶置序列）再经过任何移动也不可能变为奇异排列（奇置序列）.到此，我们就完全掌握十五子游戏的奥秘了.因为我们不但能把它排成最终状况，而且能预先就知道它能不能排成正常排列，这只要简单计算一下序列倒置数的奇偶性，且看一下空格在第几行就行了.就这样，我们仅仅使用了一点点数学概念就把神秘的十五子游戏变得十分简单明了.

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