附录4 “14-15”智力玩具的解答

首先给出结论：这个问题是无解的！

为更好地解答这个问题，我们需要引入一个定义：逆序数Dp.所谓逆序数是指前面的数字大于后面的数字的总对数，学过线性代数的同学可能对这个定义不会陌生，毕竟行列式的计算就得用到逆序数。而逆序数依然可以用在这个游戏的解答之中。

我们先从简单的情况开始讨论。我们可以先假设一个排序正确的木板如图(a)，这时我们移动右下角的三个方块，使得移动后的形状与原来相同，得到图(b).计算逆序数Dp=6.之后我们再移动右下角的六个方块得到图(c).计算逆序数Dp=12.以此类推，我们会发现，如果从排序正确的图(a)开始移动，那么最后逆序数一定为偶数。

下面给出逆序数变化为偶数的较为严谨的证明。

首先我们需要明确的一点是由图(a)变化到图(b)的过程中空格的位置是不变的。

注意到方块在移动时有水平和垂直两种方式，于是分开讨论。

水平移动时，逆序数没有变化，于是其奇偶性也没有变化，$∆$Dp=0;

垂直移动时，需要跨越三个方块，这会导致方块与相邻的这三个方块的相对顺序全部反转，由于对称性，向上移动与向下移动奇偶性变化相同，不妨只考虑向下移动的情形。假设这四个方块原来的逆序数为m，则移动后逆序数变为3-m，于是全体逆序数的变化量为3-2m.此时，空格也向上移动了一格。由于方块垂直移动时空格只改变行号，于是空格行号就是此问题的不变量。为使空格重新回到原位置，方块垂直移动的次数一定为偶数，故$∆$Dp=2k(3-2m).逆序数奇偶性不变。

综上，逆序数的奇偶性在移动过程中始终不变，因为一开始Dp=0，为偶数，故无论如何移动，逆序数始终为偶数。证毕。

回头再来看游戏里的逆序数，为奇数，因此永远也不可能排成正确的顺序。

这里无论怎么移动逆序数始终为偶数这一性质可以看作该问题中的“不变量”，不变量在数学中诸如拓扑等很多领域皆有广泛的应用。