关于数字拼图的问题数字1-8在3
这个问题的答案是不能。其证明是用奇偶性。我们规定一个次序是从左到右从上往下(我们忽略空格,必要的时候用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 的方格来说,两个奇排列可以互相变换过去,两个偶排列也可以互相变换过去,但一个奇排列和一个...全部
这个问题的答案是不能。其证明是用奇偶性。我们规定一个次序是从左到右从上往下(我们忽略空格,必要的时候用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) 不变。
总之,变换后的排列和原排列奇偶性相同。
至于结论“两个奇排列可以互相变换过去,两个偶排列也可以互相变换过去”,可以设计一种方法证明每个排列都可变为上面提到的两个排列之一, 这两个排列可称标准形式。
比如一种方法是先排好第一行,再处理剩下两行。这里不赘述。收起