萨姆·劳埃德的无解之谜

1880 年，就像一个世纪之后的魔方那样，一个机械智力游戏风靡美国。这个机械游戏就是 15 - 数字推盘游戏。时至今日，我们仍能找到它的身影。游戏的目标是通过在一个 4×4 的板中上下左右滑动 15 个有编号的方块，来让它们按编号顺序排列好。

那个时候，著名的美国智力游戏设计师萨姆·劳埃德悬赏 1000 美元（约合现在的 25 000 美元）求解他的 15 - 数字推盘游戏。劳埃德的游戏和一般游戏相差无几，但它的初始方块配置很特别：方块按数字顺序排列，但是 14 和 15 是反过来的（图 2.1）。^[9]

图 2.1　萨姆·劳埃德的 15- 数字推盘游戏（图文：谜题大陆的 14-15 谜题）（S. Loyd, 1914,《萨姆·劳埃德的智力游戏百科》，纽约：Lamb 出版社）

劳埃德可不是乱花钱的人。他知道自己永远不用付钱，因为在 1879 年，两名数学家证明了这样的初始配置是不可解的。^[10] 让我们来看看为什么。

要解决 15 - 数字推盘游戏，我们必须把编号按从左到右、从上到下的顺序用线连起来。从结果来说，为了让证明更简单，我们需要改变胜利条件：方块的编号需要按蛇形排列——第一行从左到右，第二行从右到左，第三行从左到右，第四行从右到左。不过我们不会改变游戏规则。相对地，可以想象成我们把新的编号贴到了方块上——把 8 贴到 5 上，把 7 贴到 6 上，以此类推（图 2.2）。

图 2.2　重新编号的 15- 数字推盘游戏

假设我们拿到了一个打乱顺序的 15 - 数字推盘游戏，如图 2.3 所示。我们把编号拿出来，然后按蛇形顺序列出，并且跳过空格。在这个例子中，这个列表是 2、13、5、1、4、12、11、10、3、14、15、6、9、7、8。对于表中的每个数字，我们都记录它右边的数中有多少个比它小。2 的右边 4 只有 1 个比它小的数，13 的右边有 11 个数比它小，以此类推。然后我们把这些数加起来，得到的和是 44。也就是说，一共有 44 对方块按错误的顺序排列了，这也被叫作逆序对。最终的答案中应该没有逆序对。表 2.1 列出了我们的例子中的逆序对。

4这里的右边是指在新的蛇形顺序下。——译者注

图 2.3　一个打乱顺序的 15- 数字推盘游戏

表 2.1　我们的 15- 数字推盘游戏中的逆序对

现在我们把一个方块推入空格，然后看看逆序对有什么变化。如果把一个方块向左或者向右推入空格，比如例子中的 14 或者 15，那么序列没有改变，因此逆序对的数量也不变。如果我们在蛇形排列换行的地方把一个方块上移或者下移，序列也不会改变。如果我们在其他地方上移或者下移方块，逆序对的数量就会改变了。但是这不会影响所有的方块，这样的一步只会影响到 3 个、5 个或者 7 个方块。这取决于空格的位置，以及究竟是哪个方块被推进了空格。只有这几个方块的逆序对会被影响。

如果我们下移 12，它就被挪到了 14 和 15 之间。所以它只会影响 12、11、10、3 和 14。注意，12 比 11、10 还有 3 都大，但是小于 14。所以，当它被移走之后，它的逆序对数量减少了 3，但 14 的逆序对数量增加了 1。这样，总逆序对数量就减少了 2，变成了 42。同样，如果我们把 9 上移，序列会从 15、6、9 变成 9、15、6。因为 9 比 6 大，比 15 小，它的逆序对数量会增加 1，15 的逆序对数量会减少 1。因此，总的逆序对数量保持不变，如表 2.2 所示。

表 2.2　移动方块 12 和方块 9 之后的逆序对情况

通常，垂直移动会影响 个方块，其中 可能是 2、4 或者 6。我们移动的方块比剩下的 个方块中的 个小，比 个大。如果我们下移方块，总的逆序对数量变化就是 ；如果我们上移方块，这个变化就是 。这个变化量无关紧要，重要的是这些数都是偶数。所以，每次移动之后，逆序对总数的奇偶性保持不变——原来是奇数的还会是奇数，原来是偶数的也还会是偶数。如果初始配置有偶数个逆序对，那么这个和在游戏中一直都会是偶数。我们不可能通过移动方块来让这个和变成奇数。同样，如果和开始是奇数，那么它也一直都会是奇数。

我们再来考察劳埃德谜题。他把 14 和 15 调换了顺序。在我们重新编号的例子中，调换了顺序的方块是 13 和 14。正如我们在表 2.3 中看到的，劳埃德谜题中逆序对数量是 1，而 1 是个奇数。但游戏目标是让方块按数字顺序排列，目标排列的逆序对数量是 0，而 0 是个偶数。因为游戏中逆序对数量的奇偶性不变，所以我们不可能解开劳埃德谜题并拿走 1000 美元！

表 2.3　劳埃德谜题中逆序对的数量和目标排列中逆序对数量的奇偶性不同