关于十五子的游戏

陈景润

在一张纸上画一个正方形，并把它分成大小相同的16个小方格，再剪出15个大小相同的正方形纸板，而这些正方形纸板面积稍小于方格的面积.在这些小纸板上写上1到15这15个数，这样我们就可以来玩“十五子游戏”了. 把这15个纸板任意放到这16个小方格中去（如图1）. 由于每个小方格只能放1个，因而，有1个小方格是空着的.游戏规定：当且仅当纸板与空格相邻时，这个纸板才能和空格相互调换位置，纸板相互之间不能调换位置．现在的问题是能不能经过有限次的移动以后，把这15个子的顺序排为图2所示的样子. 我们知道，把这15个纸板按任意顺序放到这16个小方格中去的方法共有16 × 15 × … × 3 × 2＝20 922 789 888 000（种）. 若每一种都要来试一下能不能排成图2所示的样子，那得花费多少时间啊！于是，我们只能多动脑筋，去找出这个游戏的规律.

我们不难看出，任一纸板都能经过几次和空格相互对换位置后，移到这16个小方格中的任一指定的方格中，为了叙述方便，我们将这16个小方格标上号码，如图3所示. 另外我们把15个纸板分别称为1，2，3，…，15．首先，我们可以把“1”移到一号位置上．然后，能否把“2”移到二号位置上呢？这也是可以做到的.若“2”在第一列，我们可以把它移出第一列，也可以把空格移出第一列，然后第一列不动，而在第二、三、四列中，仿前述方法把“2”移到二号位置上.“1”“2”的位置确定后，我们不动它，用相同的方法还可以把“3”移到三号位置上去.这时如果空格不在四号位置上，要想不动“1”“2”“3”而把“4”移到四号位置上去，却一定不能够做到了.因为在四号位置右边和上边都没有方格，而左边的“3”又不能动，故只有下边的八号位置与它有联系了.但我们总可以使第一行不动，而把“4”移到八号位置上，把空格移到十二号位置上，如图4所示.在图4中，我们取三、四、七、八、十一、十二这6个方格出来而构成图5.为了方便起见，我们将这几号位置中纸板上的数字分别用甲、乙、丙来代替.然后依次把“4”往下移，甲往下移，“3”往右移，乙往上移，如图6．再把甲往左移，“4”往上移，丙往右移，就变成了图7，在图7中把甲往下移，乙往下移，“3”往左移，“4”往上移.此时“3”“4”已分别在三、四号位置上了（如图8）.

第一行排好后，不动第一行，按照安排第一行的方法，当然能够把“5”“6”“7”安排在五、六、七号位置上，把“8”安排在八号位置上去.

再来安排第三行与第四行时，就要使用不同的办法了.我们不是先排第三行，而是先排第一列下面的两个位置，即九和十三号位置.这也不难做到，因为我们可以把第一列看做第一行，按照排第一行后面两个位置的办法来安排第一列后面的两个位置.“9”和“13”都已安排好后，按上述办法，我们还能把“10”“14”也安排到十、十四号位置上，这时只剩下“11”“12”“15”这3块纸板还没有安排好.我们可以把“11”移到十一号位置上，剩下的“12”“15”可能出现下列两种情况：其一是“12”“15”都恰好移到十二及十五号位置上，如图9，这正是我们所要达到的目的.但也可能出现第二种情况，如图10.“12”排在十五号位置上，而“15”排在十二号位置上.因为图11可经过图12、图13、图14变成为图15，于是我们知道任给一个初始状态，经过上面的一系列移动后，都可以变为图16与图17两种顺序中的一种，我们称图16为“正常排列”.而移图17为“奇异排列”．应该说，作为一种游戏，讨论到此就算完了.但如果要问“奇异排列”能不能够重新移动而变为“正常排列”，哪一种初始状况能变为“正常排列”，哪一种初始状况要变为“奇异排列”，那就不得不借助于较多的数学方法了.

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