数学问题-重排九宫格与重排15 - 拼接及滑块 我爱数学网-数学爱好者的家园-中国专业化的数学论坛之一

我爱数学网-数学爱好者的家园-中国专业化的数学论坛之一

查看: 2359|回复: 0

[重排九宫] 数学问题-重排九宫格与重排15

[复制链接]

7

主题

8

帖子

154

积分

版主

Rank: 7Rank: 7Rank: 7

积分
154
发表于 2014-10-23 12:26:34 | 显示全部楼层 |阅读模式
本帖最后由 小砖头 于 2014-10-23 13:19 编辑

如下图所示,3*3的格子中有1-8  8个数字,一格只能放一个数字。我们能把第一种排列变成第二种吗(即7,8互换)?
这看似一个简单的问题,然而变换的方法却似乎极难构造。(各位看官不妨自己一试)
large_AeSh_33f100005fac118e.jpg

以下是解答,慎入




华丽的分割线
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

事实上,对于以上问题,互易两个数字,且其他保持位置不变是不可能做到的。

下面是我的一个证明:
(复习下线性代数中提到过的逆序数
在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列;逆序数为奇数的排列称为奇排列。如2431中,21,43,41,31是逆序,逆序数是4,为偶排列。)
large_FNdS_5d6c00003ea71260.jpg
首先,将3*3的格子阵中的数字按照蓝色箭头方向展开成数列,例如上图的排列,展开成数列后为
12345876.  把这个数列称为方阵展开数列

将任意两个数字互易,而其他位置不变,等价于将展开后的数列中两个数字互易,而其他位置不变。例如在Fig1中,左图展开为12345687, 右图展开为12345678, 可见展开后的数列也是8,7互易的。

对于这样的展开数列,将数字在九宫格同一行中移动是没有作用的,若将数字在列中移动,则会改变最后方阵展开数列的结果。例如在Fig.2中,将7移入空格,则等于将12345876-----> 12347586 ,称这一操作为一个变换
这个变换相当于将7插入4与5之间(见Fig.2下半部分)。
由于每个空格总是在移动数字的正上方或者正下方,所以每次变换相当于在方阵展开数列中把一个数字向前移动2位或者向后移动两位。可见每次变换后,方阵展开数列的逆序数+2,或者+0,或者-2,总之变换不改变方阵展开数列逆序数的奇偶性。
若能够将两个数字互易其他不变,则相当于改变方阵展开数列逆序数的奇偶性(两数互换逆序数+1或-1),而刚才已经证明通过变换是做不到这点的。因此不可能将两个数字互易其他不变,也就是说九宫格中的数字是不能实现任意排列的。
证毕//

令人感兴趣的是,类似的问题有前人考虑过么?我首先想到的是华容道,但是网上资料显示,这个问题和华容道没有什么关系,它最早出现在19世纪,称为重排15,该问题如下:
original_v2ot_5dbc00003f701260.jpg
能否将Fig.3中左图变换成右图?
显然这个问题是之前问题的4维形式。这个问题在19世纪曾风靡一时,从达官显贵到贩夫走卒都在研究。按照马克吐温的描述,有为此把轮船开上码头,火车忘记靠站的窘事发生。可惜这个问题同样是无解的。

类似的问题可以推广到N*N的方阵,利用刚才给出的方阵展开排列和逆序数的方法可以证明这个问题,但是证明要略作改动,不能再用刚才逆序数奇偶性了,但同样是比较容易的,这里就不再罗嗦了。

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 会员注册

本版积分规则

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc

关于我们 | 网站地图 | 我爱数学网 ( 沪ICP备16005585号-3  

GMT+8, 2019-11-13 03:09 征信网

快速回复 返回顶部 返回列表