【数学】一道怪怪的数学题


BIRDLINE

其实是老电脑里面的一个游戏。

如图1(其中一种初态),一个4×4的棋盘,上面有1~15共15个数字和一个空格(用◎表示),要求利用空格移动棋子把他们排成图2的形式(目标状态)。
10 1 11 14                     1  2  3  4
2  3 ◎  5                       5  6  7  8
8  9  4 15                      9  10 11 12
12 13 6  7                     13 14 15 ◎
(图1)                            (图2)

问题:
现有一函数f(x),x表示格子的编号(编号与图2类似,◎处为16号),f(x)的值表示从第x+1格到第16格中,较x格中的棋子的号码小的棋子个数。例如,图1中,第8格的棋子是5,故f(8)=1,同理f(14)=2。对于空格◎,定义为比任何棋子都大,如图1中f(7)=9。又如,图2中,f(1)=f(2)=…=f(16)=0。
设空格位于棋盘上第i行第j列(如图1,i=2,j=3)。

求证:
对于一个给定的初态,如果:
16
∑f(x)+i+j
x=1
和是偶数,则该初态可变换成目标状态,否则,其他任何初态都不可能变换成目标状态。

///////////////////////////////////////////////////
结论0:
若某种初态能够变换为图2的排列,则∑f(x)+i+j 是偶数。

证明:
考虑空格◎朝上、下、左、右四个方向移动的时候∑f(x)+i+j的变化量:
左、右:变化量为0;
上:设◎的格号为k,格号为k-1,k-2,k-3的格子中有m个数大于格子k-4中的数,
则此时的变化量等于2*m;
下:设◎的格号为k,格号为k+1,k+2,k+3的格子中有m个数大于格子k+4中的数,
则此时的变化量等于-2*m;
每种情况变化量都是偶数。
由于最终的目标状态的∑f(x)+i+j=8是偶数,所以结论0成立。

结论1:
在下面的2X3表格中i,j可以互换位置,其中◎可在任意一个x处。

i x x
j x

证明:

i x x
j x

==>

i x
j x x

==>

j i x
x x

==>

j x
x i x

==>

x j x
i x

==>

x j
i x x

==>

x i j
x x

==>

i j
x x x

==>

j x
i x x

得证!

由结论1,便可以得到:

结论2:
在2X3的表格中,任意两个数都可以按指定顺序移到边上的两个格中。

证明:
1.若这两个数在表中相邻,则首先利用空格子将它们拉到边上,如果顺序正确,即为所求;若不正确,利用结论1,调换位置。
2.若这两个数在表中不相邻,则首先利用空格子让它们相邻,然后同上。

结论3:
对于4X4的表格,通过适当的移动,肯定能得到下列两种结果状态之一:
(1).

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15

(2).

1 2 3 4
5 6 7 8
9 10 11 15
13 14 12


其中(1)的∑f(x)+i+j =8是偶数;(2)的∑f(x)+i+j =13是奇数。

证明:
依靠结论2,对于任何一个初态排列,我们可以依次将下列数对放到正确位置:
(1,2),(3,4),(5,6),(7,8),(9,13),(10,14),最后将11移到正确位置,◎移到角上,则必得到如结论中所述的两种状态之一,根据结论0,(2)不可能变换为(1)。由此可知若初态的∑f(x)+i+j是偶数,则它能够且只能变换成为(1);而若初态的∑f(x)+i+j是奇数,则它能够且只能变换成为(2)。

BIRDLINE

【更多趣味内容】

猫捉老鼠趣题系列

书籍:人工智能

数学猜想:有关孪生素数的一个有趣猜想

上帝的杰作系列之二:完美等式

上帝的杰作系列之一:神奇的数

Math Magic 数学幻方

蝴蝶,螺旋结构和中微子

马丁·加德纳—— 一位把数学变成画卷的艺术大师

此条目发表在数学, 游戏, 程序开发分类目录,贴了, , , 标签。将固定链接加入收藏夹。