关于数字拼图的问题
数字1-8在3*3的方格内如下图排列:1 能否在九个格子范围内通过一定次数的移动(只能利用空格移动)排成123的形式?45678若能,请详细写出移动方法;若不能,请给出证明.先悬赏50分,有满意回答还有重奖.
这个问题的答案是不能。其证明是用奇偶性。我们规定一个次序是从左到右从上往下（我们忽略空格，必要的时候用B占位置）。 对给定的一个排列，定义一个“倒置”函数 N(i), N(i) 是在数字 i 前面的比 i 大的数，比如对排列 1 2 3 4 5 6 8 7 来说， N(7)=1, 其他都是 0。
把这些数字加起来，N(1)+N(2)+。。。+ N(8), 如果这个数字是奇数，我们就说这个排列是奇排列， 否则是偶排列。上面这个排列是奇排列。而 1 2 3 4 5 6 7 8 是偶排列。 对 3x3 的方格来说，两个奇排列可以互相变换过去，两个偶排列也可以互相变换过去，但一个奇排列和一个偶排列却不能互相变换。
我们证明这最后一个结论： 首先注意到， 在一行内一个数和空格左右互换不改变排列的奇偶性，因为次序没有改变。在一列内一个数和空格上下互换也不改变排列的奇偶性， 这个证明要复杂一点。不妨假设空格在下面，上下互换要改变三个数的次序及他们的倒置函数值，假设这三个数依次是 abc, 变换后次序变为 bca, 倒置函数的变化情况有三种：1)如果 a 是最大的，那么变换后 N(a) 不变，N(b) 和 N(c) 分别减少 1， N(a)+N(b)+N(c) 总和减少 2； 2) 如果 a 是最小的，变换后N(a)+N(b)+N(c)增加 2； 3）如果 a 在中间，变换后 N(a)+N(b)+N(c) 不变。
总之，变换后的排列和原排列奇偶性相同。 至于结论“两个奇排列可以互相变换过去，两个偶排列也可以互相变换过去”，可以设计一种方法证明每个排列都可变为上面提到的两个排列之一， 这两个排列可称标准形式。比如一种方法是先排好第一行，再处理剩下两行。
这里不赘述。
答：详情>>
