【数学解密】排列组合谜题：从阿基米德到鲁比克魔方

正文

请到「今天看啥」查看全文

○ 三阶魔方的超级翻转组合。 | 图片来源：Jamie Mulholland/Simon Fraser University

现在，魔方的最佳还原选手们 （比如电脑） 可以对任意打乱的魔方在不到一秒的时间内用最少步数将其还原。所以看起来似乎寻找其他最乱状态这个难题应该是可以解决的，只是得靠“蛮力”而已：让电脑对每一种组合进行最快复原，再取所有还原步数里的最大值，就可以知道那些是最乱的组合了。

可问题是，一个三阶魔方存在430亿多种组合可能。所以，即使电脑能在1秒之内为100万种组合计算出最佳复原方案，还是需要136万多年才能完成所有组合的计算。

Davidson 和 Rokicki 找到了一个巧妙的方法，能大大减少需要计算的组合，将430亿这个庞大的数字削减为几十亿。这让位于俄亥俄州的超级计算机中心只需用几天的时间就能完成这个约需32年CPU时间的计算量。

基于排列组合的机械益智玩具有很多，有的远早于魔方的存在， 如在中国古代就有 鲁班球 和 孔明锁 等 。这样的游戏在欧美国家也有很多，比如说曾在1880年风靡全美的“ 15谜题 ” （15-puzzles，一种初始状态为16宫格，其中前15个方格内填有数字，需上下左右移动方块来排序数字的游戏） 游戏。

美国的益智游戏设计师——被称为“谜题界最大的名人、伟大的普及者、天才”—— Sam Loyd，后来进一步推广了这个“15谜题”。他设立了1000美元的奖金，要提供给能够找到知道如何调换14和15位置的人。想必他早就知道这是不可能的吧，他甚至可能知道这是数学家 Wm. Woolsey Johnson 和 William E. Story 已经在1879年就证明过的定理。

请到「今天看啥」查看全文