关于十五子的游戏
2008-07-11陈景润
陈景润
在一张纸上画一个正方形,并把它分成大小相同的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格式阅读原文”