jx215 发表于 2009-2-6 20:18:42

移动数字的问题

手机上一个移动数字的游戏：
1   2   3
4   5   6
7   8空格

每次将上面数字顺序打乱，然后经过若干次的移动之后，得到上面的排列顺序。

现在的问题是，将8个数字顺序无论怎么打乱，是否移动n次后总能得到上面正确的顺序？这个结论成立或不成立能否用数学方法证明？

上面是一个3×3的方阵，假如推广到4×4、5×5......n×n能否证明这个结论？

mathe 发表于 2009-2-6 21:43:20

很简单的结论,有一半可以.可以通过奇偶置换来判断.
http://topic.csdn.net/t/20060105/18/4500419.html

winxos 发表于 2009-2-8 16:14:38

回复 2# mathe 的帖子

这个链接似乎包含了木马哈。。。
楼主说的这个游戏以前很流行的，就是那种滑板拼图的，如果其他位置都对只有两块位置交换那就会无解。

无心人 发表于 2009-2-8 17:12:57

我这里么显示木马

jx215 发表于 2009-2-9 19:40:05

有木马吗？没有提示啊。

jx215 发表于 2009-2-9 19:46:37

原帖由 mathe 于 2009-2-6 21:43 发表 http://bbs.emath.ac.cn/images/common/back.gif
很简单的结论,有一半可以.可以通过奇偶置换来判断.
http://topic.csdn.net/t/20060105/18/4500419.html

那么逆命题成立吗？比如给出任意一个排列，由上面按顺序的排列经过若干次移动后，达到这种排列。
是否也是一半可以？

winxos 发表于 2009-2-9 20:13:54

可能是我这里误报了，用的瑞星，网页一打开就被瑞星关闭了。

litaoye 发表于 2009-2-10 03:16:05

应该也是一半，推广到N*N也是一半！

原帖由 jx215 于 2009-2-9 19:46 发表 http://bbs.emath.ac.cn/images/common/back.gif
那么逆命题成立吗？比如给出任意一个排列，由上面按顺序的排列经过若干次移动后，达到这种排列。
是否也是一半可以？

mathe 发表于 2009-2-13 08:17:28

是的,推广到一般的情况也是一半.(除了1*N和N*1,2*2的情况)
而具体判别方法可以如下,先适当移动是的开局和结局的空格位置相同.
然后通过两两交换非空格位置的数字变化到结局的局面.如果这个过程交换数字的次数是偶数,那么可以从开局到达结局,不然不能
页: [1]
查看完整版本: 移动数字的问题